- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <queue>
- using namespace std;
- //#define DEBUG(x) cerr <<#x << "=" << x << endl
- const int maxn = 1e6 + 10;
- struct Edge
- {
- int v;
- int w;
- int nxt;
- }e[maxn];
- struct node
- {
- int u, d;
- bool operator <(const node& rhs) const
- {
- return d> rhs.d;
- }
- };
- int head[maxn], cnt = 0;
- int n, m;
- int dis[maxn];
- inline void addEdge(int u, int v, int w)
- {
- e[++cnt].v = v;
- e[cnt].w = w;
- e[cnt].nxt = head[u];
- head[u] = cnt;
- }
- inline void Dijkstra()
- {
- for (register int i = 1; i <= n; i++) dis[i] = 0x7fffffff;
- dis[1] = 0;
- priority_queue<node> Q;
- Q.push((node){1,0});
- while (!Q.empty())
- {
- node fr = Q.top();
- Q.pop();
- int u = fr.u;
- int d = fr.d;
- if (d != dis[u]) continue;
- for (register int i = head[u]; i; i = e[i].nxt)
- {
- int v = e[i].v;
- int w = e[i].w;
- if (dis[u] + w < dis[v])
- {
- dis[v] = dis[u] + w;
- Q.push((node){v,dis[v]});
- }
- }
- }
- }
- int main()
- {
- scanf("%d%d", &n, &m);
- for (register int i = 1; i <= m; i++)
- {
- int x, y, z;
- scanf("%d%d%d", &x, &y, &z);
- addEdge(x, y, z);
- addEdge(y, x, z);
- }
- Dijkstra();
- printf("%d\n", dis[n]);
- return 0;
- }
[OI - 模板] 堆优化 Dijkstra
来源: http://www.bubuko.com/infodetail-2837608.html