今天我刷题了吗
搜索文档…
Dijkstra 算法
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const ll _inf(0x3f3f3f3f3f3f3f3f);
9
const int mod(1e9 + 7);
10
const int maxn(1e5 + 10);
11
const int maxm(2e5 + 10);
12
int ecnt, head[maxn];
13
ll dis[maxn];
14
bool vis[maxn];
15
16
struct edge {
17
int to, wt, nxt;
18
} edges[maxm];
19
20
template<typename T = int>
21
inline const T read()
22
{
23
T x = 0, f = 1;
24
char ch = getchar();
25
while (ch < '0' || ch > '9') {
26
if (ch == '-') f = -1;
27
ch = getchar();
28
}
29
while (ch >= '0' && ch <= '9') {
30
x = (x << 3) + (x << 1) + ch - '0';
31
ch = getchar();
32
}
33
return x * f;
34
}
35
36
template<typename T>
37
inline void write(T x, char c)
38
{
39
if (x < 0) {
40
putchar('-');
41
x = -x;
42
}
43
if (x > 9) write(x / 10, false);
44
putchar(x % 10 + '0');
45
if (c) putchar(c);
46
}
47
48
void addEdge(int u, int v, int w)
49
{
50
edges[ecnt].to = v;
51
edges[ecnt].wt = w;
52
edges[ecnt].nxt = head[u];
53
head[u] = ecnt++;
54
}
55
56
void dijkstra(int src)
57
{
58
priority_queue<p, vector<p>, greater<p>> q;
59
q.push(p(0, src));
60
dis[src] = 0;
61
while (not q.empty()) {
62
int u = q.top().second;
63
q.pop();
64
if (vis[u]) continue;
65
vis[u] = true;
66
for (int i = head[u]; ~i; i = edges[i].nxt) {
67
int v = edges[i].to, w = edges[i].wt;
68
if (dis[v] > dis[u] + w) {
69
dis[v] = dis[u] + w;
70
q.push(p(dis[v], v));
71
}
72
}
73
}
74
}
75
76
int main()
77
{
78
#ifdef ONLINE_JUDGE
79
#else
80
freopen("input.txt", "r", stdin);
81
#endif
82
memset(head, -1, sizeof head);
83
memset(dis, 0x3f, sizeof dis);
84
int n = read(), m = read(), s = read();
85
while (m--) {
86
int u = read(), v = read(), w = read();
87
addEdge(u, v, w);
88
}
89
dijkstra(s);
90
for (int i = 1; i <= n; ++i) {
91
write(dis[i] == _inf ? INT_MAX : dis[i], i == n ? '\n' : ' ');
92
}
93
return 0;
94
}
Copied!
最近更新 1yr ago
复制链接