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 |
|
|
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 |