G

Dejkstra

public
Guest Apr 02, 2024 Never 16
Clone
C++ paste1.cpp 57 lines (45 loc) | 1.15 KB
1
#include <vector>
2
#include <iostream>
3
#include <map>
4
#include <algorithm>
5
#include <queue>
6
#include <set>
7
8
using namespace std;
9
10
11
12
int main() {
13
int n, m;
14
cin >> n >> m;
15
vector<pair<int, int>> g[n];
16
17
for (int i = 0; i < m; i++ ){
18
int v, u, w;
19
cin >> v >> u >> w;
20
v--; u--;
21
g[v].push_back({u, w});
22
g[u].push_back({v, w});
23
}
24
25
vector<int> d(n, INT_MAX);
26
d[0] = 0;
27
28
set<pair<int, int>> s;
29
for (int i = 0; i < n; i++) {
30
s.insert({d[i], i});
31
}
32
33
for (int i = 0; i < n; i++) {
34
pair<int, int> s_begin = *s.begin();
35
int v = s_begin.second;
36
37
s.erase(s_begin);
38
39
for (int j = 0; j < g[v].size(); j++) {
40
int to = g[v][j].first;
41
int w = g[v][j].second;
42
43
if (d[v] + w < d[to]) {
44
s.erase({d[to], to});
45
s.insert({d[v] + w, to});
46
d[to] = d[v] + w;
47
}
48
}
49
}
50
// O(n^2 + m)
51
// O(n + m log n)
52
// if m = n^2: первое лучше
53
54
for (int i = 0; i < n; i++) {
55
cout << d[i] << " ";
56
}
57
}