Submission #3566136
Source Code Expand
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Predicate;
public class Main {
static int N, M, R, T;
static Edge[] E;
public static void main(String[] args) {
FastScanner sc = new FastScanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
R = sc.nextInt();
T = sc.nextInt();
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 long solve() {
Edge[][] G = adjB(N, E);
State[] dist = new State[N];
PriorityQueue<State> q = new PriorityQueue<>();
long ans = 0;
for (int i = 0; i < N; i++) {
ans += count(i, G, dist, q);
}
return ans;
}
static long count(int goal, Edge[][] G, State[] dist, PriorityQueue<State> q) {
Arrays.fill(dist, null);
State start = new State(goal, 0);
q.add( start );
dist[goal] = start;
while(!q.isEmpty()) {
State s = q.poll();
if( dist[s.a].d != s.d ) continue;
for (Edge e : G[s.a]) {
State next = new State(e.opposite(s.a), s.d + e.c);
if( dist[next.a] == null || dist[next.a].d > next.d ) {
dist[next.a] = next;
q.add( next );
}
}
}
// td/T < rd/R となる個数を数える
Arrays.sort(dist);
int cnt = 0;
if( R >= T ) {
for (int ti = 1; ti < N; ti++) {
int td = dist[ti].d;
// td/T < rd/R => td*R < rd*T
int rLoseMin = findMinimum(dist, ti+1, N, r -> td * R < r.d * T );
cnt += N - rLoseMin;
}
} else {
for (int ri = 1; ri < N; ri++) {
int rd = dist[ri].d;
// 遠すぎて亀が負ける場所を数える
int tWinMax = findMaximum(dist, ri+1, N, t -> t.d * R <= rd * T );
cnt += N - tWinMax - 1;
}
}
return cnt;
}
static <A> int findMaximum(A[] array, int lo, int hi, Predicate<A> p) {
while( lo < hi ) {
int mid = ((hi - lo) >>> 1) + lo;
if( p.test(array[mid]) ) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo - 1;
}
static <A> int findMinimum(A[] array, int lo, int hi, Predicate<A> p) {
while( lo < hi ) {
int mid = ((hi - lo) >>> 1) + lo;
if( p.test(array[mid]) ) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
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;
}
static class State implements Comparable<State> {
int a, d;
public State(int a, int d) {
this.a = a;
this.d = d;
}
@Override
public int compareTo(State o) {
return Integer.compare(d, o.d);
}
}
static class Edge {
int a, b, c;
public Edge(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
public int opposite(int n) {
return n == a ? b : a;
}
}
@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 |
C - ウサギとカメ |
User |
kusomushi |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
0 |
Code Size |
5691 Byte |
Status |
WA |
Exec Time |
2848 ms |
Memory |
88364 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample-01.txt, subtask0_sample-02.txt |
All |
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample-01.txt |
AC |
191 ms |
24404 KB |
subtask0_sample-02.txt |
AC |
145 ms |
24148 KB |
subtask1_01.txt |
AC |
174 ms |
25940 KB |
subtask1_02.txt |
AC |
166 ms |
25940 KB |
subtask1_03.txt |
AC |
164 ms |
23508 KB |
subtask1_04.txt |
AC |
163 ms |
26324 KB |
subtask1_05.txt |
AC |
228 ms |
29780 KB |
subtask1_06.txt |
WA |
226 ms |
32212 KB |
subtask1_07.txt |
AC |
366 ms |
43316 KB |
subtask1_08.txt |
WA |
391 ms |
43044 KB |
subtask1_09.txt |
AC |
1357 ms |
61396 KB |
subtask1_10.txt |
AC |
1402 ms |
45316 KB |
subtask1_11.txt |
AC |
936 ms |
52940 KB |
subtask1_12.txt |
WA |
2584 ms |
88364 KB |
subtask1_13.txt |
AC |
2691 ms |
45364 KB |
subtask1_14.txt |
AC |
2848 ms |
86876 KB |
subtask1_15.txt |
AC |
2107 ms |
66580 KB |
subtask1_16.txt |
AC |
2817 ms |
60084 KB |