-
Notifications
You must be signed in to change notification settings - Fork 6
/
Dijkstra- Shortest Reach 2.cpp
84 lines (67 loc) · 1.86 KB
/
Dijkstra- Shortest Reach 2.cpp
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 <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
class Node {
public:
int id;
unsigned int distance;
vector<pair<Node *, int>> adjacent;
Node(int id)
: id(id), distance(-1)
{ }
};
int main() {
int t;
scanf("%d", &t);
for (int i = 0; i < t; i++) {
int n, m;
scanf("%d %d", &n, &m);
Node** nodes = new Node*[n + 1];
for (int j = 1; j <= n; j++) {
nodes[j] = new Node(j);
}
for (int j = 0; j < m; j++) {
int x, y, r;
scanf("%d %d %d", &x, &y, &r);
Node *u = nodes[x];
Node *v = nodes[y];
u->adjacent.emplace_back(v, r);
v->adjacent.emplace_back(u, r);
}
int s;
scanf("%d", &s);
priority_queue<pair<int, Node*>> pq;
nodes[s]->distance = 0;
pq.push(make_pair(0, nodes[s]));
while (!pq.empty()) {
const auto d = pq.top().first;
const auto u = pq.top().second;
pq.pop();
if (d > u->distance) {
continue;
}
for (const auto &pair : u->adjacent) {
const auto v = pair.first;
const auto e = pair.second;
if (v->distance > d + e) {
v->distance = d + e;
pq.push(make_pair(d + e, v));
}
}
}
bool first = true;
for (int j = 1; j <= n; j++) {
if (j == s) {
continue;
}
cout << (first ? "" : " ") << (int)nodes[j]->distance;
first = false;
}
cout << endl;
}
return 0;
}