문제
풀이
다익스트라 문제이다. 기본 다익스트라에서 크게 다를게 없다. Reference에서 코드를 가져왔다. 직접 작성한 코드는 시간초과가 계속 일어나는걸 보아, 다른 성공한 코드에서는 while문 안에서 continue를 통해 시간 절약을 해주는 것이 차이가 있는 것 같다.
소스 코드
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
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
vector<pair<int, int>>g[1004];
bool check[1004];
int dis[1004];
int ans[1004][2]; // [0] = 이전 노드 [1] = 몇 개의 도시를 거쳐왔는지
int main() {
int n, m, start, end, u, v, e;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> u >> v >> e;
g[u].push_back(make_pair(v, e));
}
cin >> start >> end;
memset(dis, 127, sizeof(dis));
dis[start] = 0;
ans[start][0] = 0, ans[start][1] = 1; // 출발, 도착 도시도 포함
priority_queue < pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
pq.push(make_pair(0, start));
while (!pq.empty()) {
int ver = pq.top().second;
int wei = pq.top().first;
pq.pop();
if (check[ver] == true)continue;
check[ver] = true;
if (dis[ver] != wei) continue;
for (int i = 0; i < g[ver].size(); i++) {
int next = g[ver][i].first;
int www = g[ver][i].second;
if (dis[ver] + www < dis[next]) {
dis[next] = dis[ver] + www;
ans[next][0] = ver; // 이전 노드 (즉 어디서 왔는지, 세 번째 출력 조건)
ans[next][1] = ans[ver][1] + 1; // 몇 번째로 왔는지(두 번째 출력 조건)
pq.push(make_pair(dis[next], next));
}
}
}
cout << dis[end] << "\n";
cout << ans[end][1] << "\n";
int temp = end;
vector<int>way;
while (1) {
way.push_back(temp);
if (temp == start) break;
temp = ans[temp][0];
}
for (int i = way.size() - 1; i >= 0; i--) cout << way[i] << " ";
cout << "\n";
}
실패한 코드 (시간초과로 인해 실패했는데, while문에 continue를 통해 시간을 좀 더 절약해야할 것 같다.)
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
#include <iostream>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
int n, m, a, b;
vector<pair<int,int>> map[1001];
int before[1001];
void dijkstra(int start, int end){
priority_queue<pair<pair<int, int>, int>> q; //value, position, cnt
int dp[1001]; // i번째 도시에 도착했을 때, 비용, 지난 도시 수
for(int i = 0; i<=n; i++){
dp[i] = INF;
}
q.push(make_pair(make_pair(0, start}, 1));
dp[start] = 0;
while(!q.empty()){
int x = -q.top().first.first; // value
int y = q.top().first.second; // position
int z = q.top().second; // cnt
q.pop();
for(int i = 0; i<map[y].size(); i++){
int next_x = x + map[y][i].second;
int next = map[y][i].first;
if(dp[next] >= next_x){
dp[next] = next_x;
q.push(make_pair(make_pair(-next_x, next), z+1));
before[next] = y;
}
}
}
printf("%d\n", dp[end]);
int num = end;
vector<int> answer;
answer.push_back(end);
while(num != start){
answer.push_back(before[num]);
num = before[num];
}
printf("%d\n", answer.size());
for(int i = (int)answer.size()-1; i>=0; i--){
printf("%d ", answer[i]);
}
}
int main(){
scanf("%d", &n);
scanf("%d", &m);
for(int i = 0; i<m; i++){
int from, to, value;
scanf("%d %d %d", &from, &to, &value);
map[from].push_back({to, value});
}
scanf("%d %d", &a, &b);
dijkstra(a, b);
}
