Submission #3607508


Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, M, S, T;
    static Edge[] E;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        S = sc.nextInt()-1;
        T = sc.nextInt()-1;
        E = new Edge[M];
        for (int i = 0; i < M; i++) {
            E[i] = new Edge(sc.nextInt()-1, sc.nextInt()-1, sc.nextInt());
        }

        System.out.println(solve());
    }

    static class Edge {
        final int a, b, d;

        public Edge(int a, int b, int d) {
            this.a = a;
            this.b = b;
            this.d = d;
        }

        int opposite(int x) {
            return a == x ? b : a;
        }
    }

    static class State {
        int a;
        int d;

        public State(int a, int d) {
            this.a = a;
            this.d = d;
        }
    }

    static int MOD = 1_000_000_007;
    static long INF = Long.MAX_VALUE / 2;

    static long solve() {
        Edge[][] G = adjB(N, E);

        Result r = calc(G);
        int collision = countCollision(G, r.dist);
        // System.out.println("dist=" + r.dist + " time=" + r.time + " collision=" + collision);
        return ((long)r.time * r.time - collision) % MOD;
    }

    static class Result {
        long dist;
        int time;

        public Result(long dist, int time) {
            this.dist = dist;
            this.time = time;
        }
    }

    static Result calc(Edge[][] G) {
        long[] dist = new long[N];
        int[] time = new int[N];
        Arrays.fill(dist, INF);
        Arrays.fill(time, -1);

        ArrayDeque<State> q = new ArrayDeque<>();
        q.add(new State(S, 0));
        dist[S] = 0;
        time[S] = 1;

        while( !q.isEmpty() ) {
            State s = q.poll();

            for (Edge e : G[s.a]) {
                int next = e.opposite(s.a);
                int nd = s.d + e.d;
                if( dist[next] > nd ) {
                    dist[next] = nd;
                    time[next] = time[s.a];
                    q.add( new State(next, nd) );

                } else if( dist[next] == nd ) {
                    time[next] += time[s.a];
                    time[next] %= MOD;
                }
            }
        }
        return new Result(dist[T], time[T]);
    }

    static int countCollision(Edge[][] G, long st) {
        long[] dist = new long[N];
        int[] time = new int[N];
        int[] collision = new int[N];
        Arrays.fill(dist, INF);
        Arrays.fill(time, -1);

        ArrayDeque<State> q = new ArrayDeque<>();
        q.add(new State(S, 0));
        dist[S] = 0;
        time[S] = 1;
        collision[S] = 0;

        while( !q.isEmpty() ) {
            State s = q.poll();

            for (Edge e : G[s.a]) {
                int next = e.opposite(s.a);
                int nd = s.d + e.d;

                if( dist[next] > nd ) {
                    dist[next] = nd;
                    time[next] = time[s.a];
                    if( isCollision(dist[s.a], e, st) ) {
                        collision[next] = time[s.a];
                    } else {
                        collision[next] = collision[s.a];
                    }

                    q.add( new State(next, nd) );

                } else if( dist[next] == nd ) {
                    time[next] += time[s.a];
                    time[next] %= MOD;
                    if( isCollision(dist[s.a], e, st) ) {
                        collision[next] += (collision[s.a] + time[s.a]);
                        collision[next] %= MOD;
                    } else {
                        collision[next] += collision[s.a];
                        collision[next] %= MOD;
                    }
                }
            }
        }
        return collision[T];
    }

    // (dist[n.a], dist[n.a] + e.d]の間にcollisionするかどうか
    static boolean isCollision(long dist, Edge e, long st) {
        long tak_s = dist;
        long aok_s = (st - dist);
        return aok_s - tak_s <= e.d * 2 // (5, 10] [10, 15)
                && tak_s < aok_s; // (5, 10] [6, 11)
    }

    static Edge[][] adjB(int n, Edge[] E) {
        Edge[][] adj = new Edge[n][];
        int[] cnt = new int[n];
        for (Edge e : E) {
            cnt[e.a]++;
            cnt[e.b]++;
        }
        for (int i = 0; i < n; i++) {
            adj[i] = new Edge[cnt[i]];
        }
        for (Edge e : E) {
            adj[e.a][--cnt[e.a]] = e;
            adj[e.b][--cnt[e.b]] = e;
        }
        return adj;
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}

Submission Info

Submission Time
Task E - Avoiding Collision
User kusomushi
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 6460 Byte
Status WA
Exec Time 1209 ms
Memory 109288 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 4
AC × 7
WA × 15
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, sample01.txt, sample02.txt, sample03.txt, sample04.txt
Case Name Status Exec Time Memory
01.txt AC 398 ms 63048 KB
02.txt WA 929 ms 93072 KB
03.txt WA 736 ms 70212 KB
04.txt WA 795 ms 74080 KB
05.txt WA 465 ms 62292 KB
06.txt WA 712 ms 71528 KB
07.txt WA 765 ms 73272 KB
08.txt WA 350 ms 43204 KB
09.txt WA 811 ms 74936 KB
10.txt WA 808 ms 73788 KB
11.txt AC 761 ms 73444 KB
12.txt AC 750 ms 73280 KB
13.txt WA 718 ms 73372 KB
14.txt WA 748 ms 70784 KB
15.txt WA 1152 ms 109288 KB
16.txt WA 1180 ms 103916 KB
17.txt WA 1156 ms 106756 KB
18.txt WA 1209 ms 106664 KB
sample01.txt AC 75 ms 20052 KB
sample02.txt AC 77 ms 21460 KB
sample03.txt AC 75 ms 20692 KB
sample04.txt AC 75 ms 20564 KB