-
Notifications
You must be signed in to change notification settings - Fork 0
/
BJ16118.java
99 lines (77 loc) · 2.62 KB
/
BJ16118.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package BJ;
import java.io.*;
import java.util.*;
public class BJ16118 {
static class Node implements Comparable<Node>{
int n,o;
double w;
public Node(int n, double w) {
this.n = n;
this.w = w;
}
public Node(int n, double w, int o) {
this.n = n;
this.w = w;
this.o = o;
}
@Override
public int compareTo(Node o) {
return Double.compare(this.w,o.w);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
List<Node>[] node = new List[N];
for (int i = 0; i < N; i++) {
node[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
int d = Integer.parseInt(st.nextToken());
node[a].add(new Node(b,d));
node[b].add(new Node(a,d));
}
PriorityQueue<Node> pq = new PriorityQueue();
// 늑대
double[][] wolf = new double[2][N];
int[] fox = new int[N];
Arrays.fill(wolf[0], Integer.MAX_VALUE);
Arrays.fill(wolf[1], Integer.MAX_VALUE);
Arrays.fill(fox, Integer.MAX_VALUE);
wolf[0][0]=0;
fox[0]=0;
// 여우
for (Node n:node[0]) pq.add(n);
while(!pq.isEmpty()){
Node now = pq.poll();
if (fox[now.n]!=Integer.MAX_VALUE) continue;
fox[now.n] = (int) now.w;
for(Node n:node[now.n]){
if (fox[n.n]!=Integer.MAX_VALUE) continue;
pq.add(new Node(n.n, now.w + n.w));
}
}
// 늑대
for (Node n:node[0]) pq.add(new Node(n.n,n.w*0.5,1));
while(!pq.isEmpty()){
Node now = pq.poll();
int no = (now.o+1)%2;
if (wolf[now.o][now.n]!=Integer.MAX_VALUE) continue;
wolf[now.o][now.n] = now.w;
for(Node n:node[now.n]){
if (wolf[no][n.n]!=Integer.MAX_VALUE) continue;
pq.add(new Node(n.n, now.w + n.w*(no==1?0.5:2),no));
}
}
int cnt=0;
for (int i = 1; i < N; i++) {
if (fox[i] < Math.min(wolf[1][i], wolf[0][i])) cnt++;
}
System.out.print(cnt);
}
}