Submission #3609238
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 implements Comparable<State> {
int a;
long d;
public State(int a, long d) {
this.a = a;
this.d = d;
}
@Override
public int compareTo(State o) {
return Long.compare(d, o.d);
}
}
static int MOD = 1_000_000_007;
static long INF = Long.MAX_VALUE / 2;
static long solve() {
Edge[][] G = adjB(N, E);
Result rs = calc(G, S);
Result rt = calc(G, T);
long dist = rs.dist[T];
long collision = 0;
for (int i = 0; i < N; i++) {
if( rs.dist[i] == dist / 2 && rt.dist[i] == dist / 2 ) {
collision += (long)rs.time[i] * rt.time[i] % MOD;
collision %= MOD;
}
}
for (Edge e : E) {
int a = rs.dist[e.a] < rs.dist[e.b] ? e.a : e.b;
int b = e.opposite(a);
int d = e.d;
if( rs.dist[a] + d == rs.dist[b]
&& rs.dist[b] + rt.dist[b] == dist
// && rs.dist[a] + rt.dist[a] == dist 必要ないっぽい
&& rs.dist[a] < rt.dist[a]
&& rs.dist[b] > rt.dist[b] )
{
long ab = (long)rs.time[a] * rt.time[b] % MOD;
collision += ab * ab % MOD;
collision %= MOD;
}
}
int time = rs.time[T];
return ((long)time * time - collision + MOD) % MOD;
}
// (v, w) intersect (x, y)
static boolean isCross(long v, long w, long x, long y) {
if( v <= x ) {
return x < w;
} else {
return v < y;
}
}
static class Result {
long[] dist;
int[] time;
public Result(long[] dist, int[] time) {
this.dist = dist;
this.time = time;
}
}
static Result calc(Edge[][] G, int from) {
long[] dist = new long[N];
int[] time = new int[N];
Arrays.fill(dist, INF);
Arrays.fill(time, -1);
PriorityQueue<State> q = new PriorityQueue<>();
q.add(new State(from, 0));
dist[from] = 0;
time[from] = 1;
while( !q.isEmpty() ) {
State s = q.poll();
if( dist[s.a] != s.d ) continue;
for (Edge e : G[s.a]) {
int next = e.opposite(s.a);
long 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, time);
}
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 |
5869 Byte |
Status |
WA |
Exec Time |
560 ms |
Memory |
64616 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 |
507 ms |
61672 KB |
02.txt |
AC |
518 ms |
62064 KB |
03.txt |
AC |
519 ms |
63988 KB |
04.txt |
AC |
506 ms |
62496 KB |
05.txt |
AC |
541 ms |
63640 KB |
06.txt |
AC |
464 ms |
59172 KB |
07.txt |
AC |
475 ms |
60660 KB |
08.txt |
AC |
330 ms |
46572 KB |
09.txt |
WA |
560 ms |
61980 KB |
10.txt |
WA |
526 ms |
62592 KB |
11.txt |
AC |
497 ms |
63844 KB |
12.txt |
AC |
494 ms |
64616 KB |
13.txt |
WA |
557 ms |
64460 KB |
14.txt |
WA |
473 ms |
62296 KB |
15.txt |
WA |
515 ms |
62392 KB |
16.txt |
WA |
533 ms |
63588 KB |
17.txt |
WA |
488 ms |
60476 KB |
18.txt |
WA |
505 ms |
61268 KB |
sample01.txt |
AC |
72 ms |
20692 KB |
sample02.txt |
AC |
70 ms |
17616 KB |
sample03.txt |
AC |
72 ms |
18644 KB |
sample04.txt |
AC |
72 ms |
18900 KB |