算法提高课-图论-单源最短路的扩展应用-AcWing 1137. 选择最佳线路：多源最短路、虚拟源点

题目分析

来源：acwing
分析：
本题有多组测试数据，如果对每个源点暴力使用dijkstra，会超时。

好的做法：建立虚拟源点S，让S到所有真实起点的边权为0，这样原问题就可以转换为从虚拟源点S到终点的单元最短路问题。

建立虚拟源点的写法：会TLE，对了5个点

尝试对每个起点进行dijkstra，也会TLE，结果对了7个点！！天哪。

第三次尝试:写了反向dijkstra，即从终点为起点，反向建边，结果还是TLE，对了9个点，就有点生气！

代码1（对了5个点）

#include<bits/stdc++.h> using namespace std; const int N = 1010, INF = 0x3f3f3f3f; const int M = 20010; typedef pair<int,int> PII; #define x first #define y second int n, m, s; int h[N],e[M],w[M],ne[M],idx; int dist[N]; bool st[N];void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; }int dijkstra(){memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[0] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0,0});while(heap.size()){auto t = heap.top();heap.pop();int ver = t.y, distance = t.x; if(st[ver]) continue;st[ver] = true;for(int i = h[ver]; ~i; i = ne[i]){int j = e[i];if(dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j});}}}if(dist[s] == INF) return -1;return dist[s]; }int main(){while(scanf("%d%d%d",&n, &m, &s) != -1){memset(h, -1, sizeof h);int p, q, t;while(m --){scanf("%d%d%d", &p, &q, &t);add(p, q, t);}int w;scanf("%d",&w);for(int i = 0; i< w; i++){int ver;scanf("%d",&ver);add(0,ver, 0);}printf("%d\n", dijkstra());} }

代码2（对了9个点）

#include<bits/stdc++.h> using namespace std; const int N = 1010, INF = 0x3f3f3f3f; const int M = 20010; typedef pair<int,int> PII; #define x first #define y second int n, m, s; int h[N],e[M],w[M],ne[M],idx; int dist[N]; bool st[N]; int path[N];void add(int a, int b, int c){e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; }void dijkstra(){memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0,s});dist[s] = 0;while(heap.size()){auto t = heap.top();heap.pop();int ver = t.y, distance = t.x; if(st[ver]) continue;st[ver] = true;for(int i = h[ver]; ~i; i = ne[i]){int j = e[i];if(dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j});}}} }int main(){while(scanf("%d%d%d",&n, &m, &s) != -1){memset(h, -1, sizeof h);int p, q, t;while(m --){scanf("%d%d%d", &p, &q, &t);add(q, p, t);}dijkstra();int w, res = INF;scanf("%d",&w);int ver;while(w --){cin >> ver;res = min(res, dist[ver]);}if(res == INF) res = -1;printf("%d\n", res);} }

代码3（ac：也是虚拟源点的写法，结果就ac了，真是奇了怪了！！！）

#include<bits/stdc++.h> #define x first #define y second using namespace std;typedef pair<int, int> PII; //建立虚拟源点0 const int N = 1010, M = 40010, INF = 0x3f3f3f3f; int n, m, s; int h[N], e[M], w[M], ne[M], idx; int dist[N]; bool st[N];void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; } int dijkstra() {memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 0});dist[0] = 0;while (heap.size()) {PII t = heap.top();heap.pop();int ver = t.y, distance = t.x;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; ~i; i = ne[i]) {int j = e[i];if (dist[j] > distance + w[i]) {dist[j] = distance + w[i];heap.push({dist[j], j});}}}if (dist[s] == INF) return -1;return dist[s]; } int main() {while (scanf("%d%d%d", &n, &m, &s)!= -1) {memset(h, -1, sizeof h);idx = 0;int x;while (m--) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}scanf("%d", &x);while (x--) {int stop;scanf("%d", &stop);add(0, stop, 0);}cout << dijkstra() << endl;}return 0; }

题目来源

https://www.acwing.com/problem/content/description/1139/

总结

以上是生活随笔为你收集整理的算法提高课-图论-单源最短路的扩展应用-AcWing 1137. 选择最佳线路：多源最短路、虚拟源点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。