题目链接:
https://vjudge.net/problem/POJ-3255
题目大意:
给无向图, 求 1 到 n 的次短路长度
思路:
由于边数较多, 应该使用 dijkstra 的队列优化 https://www.cnblogs.com/fzl194/p/8728018.html
用 d 数组存储最短路, 用 d2 数组存储次短路, 每次更新的时候, 先松弛更新最短路, 如果松弛更新成功, 把之前的最短路取出, 再和次短路比较, 更新次短路. 每次更新两个数组
- #include<iostream>
- #include<vector>
- #include<queue>
- #include<algorithm>
- #include<cstring>
- #include<cstdio>
- using namespace std;
- typedef pair<int, int> Pair;
- const int maxn = 5000 + 10;
- const int INF = 0x3f3f3f3f;
- int n, m;
- struct edge
- {
- int v, w;
- edge(int v, int w):v(v), w(w){}
- };
- vector<edge>G[maxn];
- int d[maxn], d2[maxn];
- void dijkstra()
- {
- memset(d, INF, sizeof(d));
- memset(d2, INF, sizeof(d2));
- d[1] = 0;
- priority_queue<Pair, vector<Pair>, greater<Pair>>q;
- q.push(Pair(0, 1));//1 为当前节点, 0 位最短距离
- while(!q.empty())
- {
- Pair now = q.top();
- q.pop();
- int dis = now.first, u = now.second;
- //cout<<dis<<" "<<u<<endl;
- if(dis> d2[u])continue;// 距离比次短距离大, 直接 continue
- for(int i = 0; i <G[u].size(); i++)
- {
- edge &e = G[u][i];
- int dis2 = dis + e.w;
- if(d[e.v]> dis2)
- {
- swap(d[e.v], dis2);//dis2 保存较小的值和后面进行比较
- q.push(Pair(d[e.v], e.v));
- }
- if(d2[e.v]> dis2 && d[e.v] <dis2)// 保证 dis2 为次短路
- {
- d2[e.v] = dis2;
- q.push(Pair(d2[e.v], e.v));// 次短路也入队列
- }
- }
- }
- cout<<d2[n]<<endl;
- }
- int main()
- {
- cin>> n>> m;
- int u, v, w;
- while(m--)
- {
- scanf("%d%d%d", &u, &v, &w);
- G[u].push_back(edge(v, w));
- G[v].push_back(edge(u, w));
- }
- dijkstra();
- }
来源: http://www.bubuko.com/infodetail-2558744.html