11657 타임머신
알고리즘(밸만포드)
1
2
1. 밸만포드로 푼다.
2. 길이는 long long으로 저장한다.
코드
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
#include <bits/stdc++.h>
using namespace std;
struct Road {
int to;
int time;
};
struct City {
vector<Road> next;
long long minTime;
int before;
};
City city[501];
list<Road> q;
int N, M;
bool generateMinTime();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
int a, b, c;
for (int i = 0; i < M; i++) {
cin >> a >> b >> c;
city[a].next.push_back({ b, c });
}
for (int i = 2; i <= N; i++)
city[i].minTime = 2000000000000;
if (generateMinTime()) {
for (int i = 2; i <= N; i++) {
if (city[i].minTime != 2000000000000)
cout << city[i].minTime << "\n";
else
cout << -1 << "\n";
}
}
else
cout << -1 << "\n";
}
bool generateMinTime() {
for (int i = 0; i < N - 1; i++) {
for (int j = 1; j <= N; j++) {
if (city[j].minTime != 2000000000000) {
for (int k = 0; k < city[j].next.size(); k++) {
Road t = city[j].next[k];
long long nt = city[j].minTime + t.time;
if (nt < city[t.to].minTime)
city[t.to].minTime = nt;
}
}
}
}
for (int j = 1; j <= N; j++) {
if (city[j].minTime != 2000000000000) {
for (int k = 0; k < city[j].next.size(); k++) {
Road t = city[j].next[k];
long long nt = city[j].minTime + t.time;
if (nt < city[t.to].minTime)
return false;
}
}
}
return true;
}