-
Notifications
You must be signed in to change notification settings - Fork 0
/
BellmanFord.java
84 lines (73 loc) · 2.09 KB
/
BellmanFord.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
/*
* TItle : Baeckjoon 11657 타임머신
* Reference :https://namu.wiki/w/%EB%B2%A8%EB%A8%BC-%ED%8F%AC%EB%93%9C%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
* */
package shortestPath;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BellmanFord {
private static final int INF = 1000000000;
private static class Edge{
public int s;
public int e;
public int w;
public Edge(int s, int e, int w){
this.s = s;
this.e = e;
this.w = w;
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //도시 수
int M = Integer.parseInt(st.nextToken()); //노선 수
int dist[] = new int[N + 1]; //dist[1]은 이미 0
Edge edges[] = new Edge[M];
boolean isCycle = false;
for (int i = 2; i <= N; i++)
dist[i] = INF;
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
edges[i] = new Edge(A, B, C);
}
//bellman-ford algorithm
for (int i = 0; i < N - 1; i++) {
for (int j = 0; j < M; j++) {
Edge cur = edges[j];
if(dist[cur.s] == INF)
continue;
if(dist[cur.e] > dist[cur.s] + cur.w)
dist[cur.e] = dist[cur.s] + cur.w;
}
}
for (int i = 0; i < M; i++) {
if(dist[edges[i].s] == INF)
continue;
if(dist[edges[i].e] > dist[edges[i].s] + edges[i].w){
isCycle = true;
break;
}
}
if(isCycle){
bw.write(-1 + "\n");
} else {
for (int i = 2; i <= N; i++) {
if(dist[i] == INF)
bw.write(-1 + "\n");
else
bw.write(dist[i] + "\n");
}
}
br.close();
bw.close();
}
}