城市间紧急救援 (25 分)【dijkstra模板 超时原因】

立志用最少的代码做最高效的表达

---

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。

第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:
2 60
0 1 3

---

最开始用dfs做，最后一个测试点超时。改为dijkstra，满分。

时间规模计算：dijkstra的时间复杂度为O(n²)，地图最大规模为500，500*500=25w，也就是最大规模为25w， 100ms大约运行100w的数据，因此可以AC

---

#include<iostream> #include<cstdio> #include<cstring> #include<stack>using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 510; //通过path存储，最终的结果一定是最优的 int G[maxn][maxn]; //地图 int num_p[maxn]; //每个城市救火队数量 int vis[maxn]; //每个点是否遍历过 int dist[maxn]; //起点距离各个点的最短距离 int sum_p[maxn]; //从出发点到城市i的救援队目的和 int path[maxn]; //以第i个节点为终点的最短路径的前一个节点的编号 int num[maxn]; //出发点到城市i的最短路径条数 int n, m, sta, fin; void dijkstra() {//初始化操作 fill(dist, dist + 510, inf);dist[sta] = 0;sum_p[sta] = num_p[sta];num[sta] = 1; //最短路径条数为1 path[sta] = -1; //初始节点为-1 for(int i = 0; i < n; i++) {int u = -1, minx = inf;for(int j = 0; j < n; j++) {if(vis[j] == 0 && minx > dist[j]) { //找最短路径 u = j;minx = dist[j];}}if(u == -1) break; //不连通vis[u] = 1; //设置为已访问for(int j = 0; j < n; j++) {//如果经过u再到j更短，则更新 if(vis[j] == 0 && dist[u] + G[u][j] < dist[j] ) {dist[j] = dist[u] + G[u][j];num[j] = num[u]; //更新最短路径条数sum_p[j] = sum_p[u] + num_p[j]; //救援队数目增加path[j] = u; //经过u点再到j点 } else if(dist[u] + G[u][j] == dist[j]) {num[j] = num[j] + num[u];if(sum_p[u] + num_p[j] > sum_p[j]) {sum_p[j] = sum_p[u] + num_p[j];path[j] = u;} }} } }int main() {cin >> n >> m >> sta >> fin; for(int i = 0; i < n; i++) cin >> num_p[i];//1、初始化图for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)G[i][j] = inf;//2、输入 for(int i = 0; i < m; i++) {int x, y, v; cin >> x >> y >> v;G[x][y] = G[y][x] = v; }//3、更新distfor(int i = 0; i < n; i++) {dist[i] = G[sta][i];} //4、dijkstradijkstra(); cout << num[fin] << ' ' << sum_p[fin] << '\n';stack<int> ss;ss.push(fin);while(path[fin] != 0) {ss.push(path[fin]);fin = path[fin];}cout << sta;while(!ss.empty()) {cout << ' ' << ss.top();ss.pop(); }return 0; }

---

耗时：

---

       ——弱小和无知不是生存的障碍，傲慢才是。

总结

以上是生活随笔为你收集整理的城市间紧急救援 (25 分)【dijkstra模板 超时原因】的全部内容，希望文章能够帮你解决所遇到的问题。

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