常用模板
一：朴素dijkstra算法模板
时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中，寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 用t更新其他点的距离 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); st[t] = true; } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
模板题 AcWing 849. Dijkstra求最短路 I
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例：
3 3 1 2 2 2 3 1 1 3 4
输出样例：
3
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=510,inf=0x3f3f3f3f; int n,m; int g[N][N]; int dist[N]; bool st[N]; int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int t = -1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); st[t] = true; } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main() { cin >> n >> m; memset(g,inf,sizeof g); while(m -- ) { int a,b,c; cin>>a>>b>>c; g[a][b] = min(g[a][b] , c); } int t = dijkstra(); if(t == inf) cout << "-1\n"; else cout << t; return 0; }
二：堆优化版dijkstra —— 模板题
时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数
typedef pair<int, int> PII; int n; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 // 求1号点到n号点的最短距离，如果不存在，则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); // first存储距离，second存储节点编号 while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; 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[n] == 0x3f3f3f3f) return -1; return dist[n]; }
模板题 AcWing 850. Dijkstra求最短路 II
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 109。
输入样例：
3 3 1 2 2 2 3 1 1 3 4
输出样例：
3
#include <iostream> #include <cstring> #include <algorithm> #include<queue> using namespace std; const int N = 200010; typedef pair<int, int> PII; int n,m; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) // 添加一条边a->b，边权为c { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; 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[n] == 0x3f3f3f3f) return -1; return dist[n]; } int main() { memset(h, -1, sizeof h); scanf("%d%d", &n, &m); while (m -- ) { int a,b,c; cin >> a >> b >> c; add(a,b,c); } int t = dijkstra(); printf("%d",t); return 0; }
1: L2-001 紧急救援 (25 分)
作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式:
输入第一行给出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
#include <iostream> #include <algorithm> #include <cstring> #include <vector> using namespace std; const int N = 510,inf = 0X3f3f3f3f; int n,m,s,d; int g[N][N]; // 存储各城市之间的道路长度 int dist[N]; // 存储从起点到当前点的距离 int jyd[N]; // 存储每个点救援队数量 int jyd_num[N]; // 到当前点能够召集的救援队数量 int pre[N]; // 保存前一个节点 int cnt[N]; // 记录道路条数 bool st[N]; // 判断当前点是否确定 vector<int>road; // 存路径 void dijkstra() { memset(dist,inf,sizeof dist); dist[s] = 0,cnt[s] = 1; for(int i=0;i<n;i++) { int t = -1; for(int j=0;j<n;j++) if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j; st[t] = true; for(int j=0;j<n;j++) { if(dist[j] > dist[t] + g[t][j]) // 换最短的路径 { dist[j] = dist[t] + g[t][j]; jyd_num[j] = jyd_num[t] + jyd[j]; cnt[j] = cnt[t]; pre[j] = t; } else if(dist[j] == dist[t] + g[t][j]) { cnt[j] += cnt[t]; if(jyd_num[j] < jyd_num[t] + jyd[j]) // 换最多的救援队 { jyd_num[j] = jyd_num[t] + jyd[j]; pre[j] = t; } } } } } int main() { memset(g,inf,sizeof g); cin >> n >> m >> s >> d; for(int i=0;i<n;i++) { cin >> jyd[i]; jyd_num[i] = jyd[i]; } while(m -- ) { int a,b,len; cin >> a >> b >> len; g[a][b] = g[b][a] = len; } dijkstra(); cout << cnt[d] << ' ' << jyd_num[d] << endl; while(d != s) { road.push_back(d); d = pre[d]; // 依次存入前一个节点 } cout << s; for(int i=road.size()-1;i>=0;i--) cout << ' ' << road[i]; return 0; }
2: L3-005 垃圾箱分布 (30 分)
大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，同时还要保证每个居民点都在距离它一个不太远的范围内。
现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。
输入格式：
输入第一行给出4个正整数：N（≤1000）是居民点的个数；M（≤10）是垃圾箱候选地点的个数；K（≤10000）是居民点和垃圾箱候选地点之间的道路的条数；DS是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号，所有的垃圾箱候选地点从G1到GM编号。
随后K行，每行按下列格式描述一条道路：
P1 P2 Dist
其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。
输出格式：
首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出No Solution。
输入样例1：
4 3 11 5 1 2 2 1 4 2 1 G1 4 1 G2 3 2 3 2 2 G2 1 3 4 2 3 G3 2 4 G1 3 G2 G1 1 G3 G2 2
输出样例1：
G1 2.0 3.3
输入样例2：
2 1 2 10 1 G1 9 2 G1 20
输出样例2：
No Solution
思路：把垃圾箱位置映射成n+1到n+m的整数，每一次用dijkstra查找当前垃圾箱点到其他居民点的距离，然后选在到所有居民点的最短距离最长的地方
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1020,inf = 0X3f3f3f3f; int n,m,k,ds; int g[N][N],dist[N]; bool st[N]; void dijstra(int u) { memset(dist,inf,sizeof dist); memset(st,0,sizeof st); dist[u] = 0; for(int i=1;i<=n+m;i++) { int t = -1; for(int j=1;j<=n+m;j++) if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j; st[t] = true; for(int j=1;j<=n+m;j++) dist[j] = min(dist[j],dist[t] + g[t][j]); } } int main() { cin >> n >> m >> k >> ds; memset(g,inf,sizeof g); while(k -- ) { string s1,s2; int len,a,b; cin >> s1 >> s2 >> len; if(s1[0] == 'G') { s1.erase(s1.begin()); a = stoi(s1) + n; } else a = stoi(s1); if(s2[0] == 'G') { s2.erase(s2.begin()); b = stoi(s2) + n; } else b = stoi(s2); g[a][b] = g[b][a] = len; } int id = 0; double min_dis = 0,ave_dis = 0; for(int i=n+1;i<=n+m;i++) { dijstra(i); int minn = inf,sum_dis = 0; int t = 0; for(int j=1;j<=n;j++) { if(dist[j] > ds) t = 1; if(minn > dist[j]) minn = dist[j]; sum_dis += dist[j]; } if(t) continue; if(minn > min_dis) // 更新居民最短距离最长的长度 { min_dis = minn; ave_dis = sum_dis * 1.0 / n; id = i; } else if(minn == min_dis) { if(ave_dis > sum_dis * 1.0 / n) // 更新最短的平均长度 { ave_dis = sum_dis * 1.0 / n; id = i; } } } if(!id) cout << "No Solution"; else { cout << 'G' << id - n << endl; printf("%.1f %.1f",min_dis,ave_dis); } return 0; }
3: L3-011 直捣黄龙 (30 分)
本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。
输入格式：
输入第一行给出 2 个正整数 N（2 ≤ N ≤ 200，城镇总数）和 K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后 N-1 行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有 K 行，每行按格式城镇1 城镇2 距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由 3 个大写英文字母组成的字符串。
输出格式：
按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式己方大本营->城镇1->…->敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
10 12 PAT DBY DBY 100 PTA 20 PDS 90 PMS 40 TAP 50 ATP 200 LNN 80 LAO 30 LON 70 PAT PTA 10 PAT PMS 10 PAT ATP 20 PAT LNN 10 LNN LAO 10 LAO LON 10 LON DBY 10 PMS TAP 10 TAP DBY 10 DBY PDS 10 PDS PTA 10 DBY ATP 10
输出样例：
PAT->PTA->PDS->DBY 3 30 210
#include <iostream> #include <algorithm> #include <cstring> #include <unordered_map> #include <vector> using namespace std; const int N = 210,inf = 0X3f3f3f3f; int n,k; int g[N][N]; // 存城镇间的距离 int num[N]; // 存城镇中的敌军数量 int sum[N]; // 从起点到当前点所杀的敌军数量 int pre[N]; // 记录前一个城镇的节点 int cnt[N]; // 这条路径解放城镇的数量 int dist[N]; // 从起点到当前点的距离 int quick[N]; // 最快进攻路径的条数 bool st[N]; // 判断这点是否走过 unordered_map<string,int>p1; unordered_map<int,string>p2; string s1,s2; void dijstra() { memset(dist,inf,sizeof dist); dist[1] = 0; cnt[1] = 1; quick[1] = 1; for(int i=1;i<=n;i++) { int t = -1; for(int j=1;j<=n;j++) if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for(int j=1;j<=n;j++) { if(dist[j] > dist[t] + g[t][j]) { dist[j] = dist[t] + g[t][j]; sum[j] = sum[t] + num[j]; cnt[j] = cnt[t] + 1; pre[j] = t; quick[j] = quick[t]; } else if(dist[j] == dist[t] + g[t][j]) { quick[j] += quick[t]; if(cnt[j] < cnt[t] + 1) { sum[j] = sum[t] + num[j]; cnt[j] = cnt[t] + 1; pre[j] = t; } else if(cnt[j] == cnt[t] + 1) { if(sum[j] < sum[t] + num[j]) { sum[j] = sum[t] + num[j]; pre[j] = t; } } } } } } int main() { memset(g,inf,sizeof g); cin >> n >> k >> s1 >> s2; p1[s1] = 1,p2[1] = s1; for(int i=2;i<=n;i++) { string name; int x; cin >> name >> num[i]; sum[i] = num[i]; p1[name] = i,p2[i] = name; } while(k -- ) { string x,y; int time; cin >> x >> y >> time; g[p1[x]][p1[y]] = g[p1[y]][p1[x]] = time; } dijstra(); vector<string>roat; // 存路径 int f1 = p1[s1],f2 = p1[s2]; while(f2 != f1) { roat.push_back(p2[f2]); f2 = pre[f2]; } cout << s1; for(int i=roat.size()-1;i>=0;i--) cout << "->" << roat[i]; cout << endl; cout << quick[p1[s2]] << ' ' << dist[p1[s2]] << ' ' << sum[p1[s2]]; return 0; }
4: AcWing 4275. Dijkstra序列(PTA 甲级 1163 Dijkstra Sequence (30 分))
Dijkstra 算法是非常著名的贪心算法之一。
它用于解决单源最短路径问题，即指定一个特定源顶点，求该顶点到给定图的所有其他顶点的最短路径。
它由计算机科学家 Edsger W. Dijkstra 于 1956 年构思并在三年后出版。
在该算法中，我们需要不断维护一个包含最短路径树中顶点的集合。
在每一步中，我们找到一个尚未在集合内且与源顶点距离最小的顶点，并将其收于集合中。
因此，通过 Dijkstra 算法，我们可以逐步生成一个有序的顶点序列，我们称之为 Dijkstra 序列。
对于一个给定的图，可能有多个 Dijkstra 序列。
例如，{5,1,3,4,2} 和 {5,3,1,2,4} 都是给定图的 Dijkstra 序列。
注意，序列中的第一个顶点即为指定的特定源顶点。
你的任务是检查给定的序列是否是 Dijkstra 序列。
输入格式
第一行包含两个整数 N 和 M，表示图中点和边的数量。
点的编号 1∼N。
接下来 M 行，每行包含三个整数 a,b,c，表示点 a 和点 b 之间存在一条无向边，长度为 c。
再一行包含整数 K，表示需要判断的序列个数。
接下来 K 行，每行包含一个 1∼N 的排列，表示一个给定序列。
输出格式
共 K 行，第 i 行输出第 K 个序列的判断，如果序列是 Dijkstra 序列则输出 Yes，否则输出 No。
数据范围
1≤N≤1000,
1≤M≤100000,
1≤a,b≤N,
1≤c≤100,
1≤K≤100,
保证给定无向图是连通图，
保证无重边和自环（官网没提，但是经实测，官网数据符合此条件）。
输入样例：
5 7 1 2 2 1 5 1 2 3 1 2 4 1 2 5 2 3 5 1 3 4 1 4 5 1 3 4 2 5 3 1 2 4 2 3 4 5 1 3 2 1 5 4
输出样例：
Yes Yes Yes No
难度：简单
时/空限制：2s / 64MB
来源：PAT甲级真题1163
思路：起始节点到当前节点的距离一定会大于等于到当前节点前一个节点的距离，所以循环判断一下就行了
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010,inf = 0x3f3f3f3f; int n,m; int g[N][N],dist[N],f[N],pre[N]; bool st[N]; void dijkstra(int u) { memset(dist,inf,sizeof dist); memset(st, 0, sizeof st); dist[u] = 0; for(int i=1;i<=n;i++) { int t = -1; for(int j=1;j<=n;j++) if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for(int j=1;j<=n;j++) { if(dist[j] > dist[t] + g[t][j]) { dist[j] = dist[t] + g[t][j]; pre[j] = t; } } } } int main() { memset(g,inf,sizeof g); scanf("%d%d", &n, &m); while (m -- ) { int a,b,c; scanf("%d%d%d", &a, &b, &c); g[a][b] = g[b][a] = c; } int k; scanf("%d",&k); while(k -- ) { for(int i=1;i<=n;i++) scanf("%d", &f[i]); dijkstra(f[1]); bool flag = false; for(int i=n;i>1;i--) if(dist[f[i]] < dist[f[i - 1]]) flag = true; if(flag) puts("No"); else puts("Yes"); } return 0; }
5: AcWing 1375. 奶牛回家
晚餐时间马上就到了，奶牛们还在各自的牧场中悠闲的散着步。
当农夫约翰摇动铃铛，这些牛就要赶回牛棚去吃晚餐。
在吃晚餐之前，所有奶牛都在自己的牧场之中，有些牧场中可能没有奶牛。
每个牧场都通过一条条道路连接到一个或多个其他牧场（可能包括其自身）。
有时，两个（可能是相同的）牧场通过一条以上的道路相连。
至少存在一个牧场与牛棚通过一条道路直接相连。
所以说，所有奶牛都能够成功的从自己的牧场沿道路返回牛棚。
聪明的奶牛们总会选择最短的路径回到牛棚之中。
每条道路都是可以双向行走的，奶牛的行走速度也都一样。
我们用 a∼z 和 A∼Y 来标记所有的牧场。
所有用大写字母标记的牧场中都存在一头奶牛，所有用小写字母标记的牧场中都不存在奶牛。
牛棚的标记为 Z，这里最初是没有奶牛的。
现在你需要确定，哪一头奶牛能够最快到达牛棚，输出它最初所在的牧场的标记，并输出它走过的路径的长度。
注意，同一字母大小写标记的两个牧场（例如，牧场 A 和牧场 a）是两个完全不同的牧场。
输入格式
第一行包含整数 P，表示连接牧场以及牛棚的道路的条数。
接下来 P 行，每行包含两个字母以及一个整数，表示被一条道路连接的两个牧场的标记，以及这条道路的长度。
输出格式
输出一个字母和一个整数，表示最快回到牛棚的牛最初所在的牧场的标记以及它走过的路径的长度。
数据保证最快回到牛棚的牛只有一头。
数据范围
1≤P≤10000,
所有道路长度均不超过 1000。
输入样例：
5 A d 6 B d 3 C e 9 d Z 8 e Z 3
输出样例：
B 11
难度：简单
时/空限制：1s / 64MB
来源：usaco training 2.4
思路：因为大写字母标记的牧场中表示都存在一头奶牛，所以我们把A ~ Z映射到1 ~ 26的数字，小写字母标记的牧场中表示不存在奶牛，所以我们把A ~ Z映射到27 ~ 57的数字，26是牛棚的位置所以我们找1 ~ 25 到26的距离最短的那一个就行了
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 110,inf = 0x3f3f3f3f; int g[N][N],dist[N]; bool st[N]; int to_check(char op) { if(islower(op)) return op - 'a' + 27; if(isupper(op)) return op - 'A' + 1; } void dijkstra(int u) { memset(dist,inf,sizeof dist); memset(st, 0, sizeof st); dist[u] = 0; for(int i=1;i<=52;i++) { int t = -1; for(int j=1;j<=52;j++) if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for(int j=1;j<=52;j++) dist[j] = min(dist[j],dist[t] + g[t][j]); } } int main() { int m; cin >> m;; memset(g,inf,sizeof g); while (m -- ) { char a,b; int c; cin >> a >> b >> c; int x = to_check(a); int y = to_check(b); g[x][y] = g[y][x] = min(g[x][y],c); // 重边选最短的 } int minn = inf,idx = 0; for(int i=1;i<26;i++) { dijkstra(i); if(dist[26] < minn) { minn = dist[26]; idx = i; } } cout << char(idx - 1 + 'A') << ' ' << minn; return 0; }
6: L3-028 森森旅游 (30 分)
好久没出去旅游啦！森森决定去 Z 省旅游一下。
Z 省有 n 座城市（从 1 到 n 编号）以及 m 条连接两座城市的有向旅行线路（例如自驾、长途汽车、火车、飞机、轮船等），每次经过一条旅行线路时都需要支付该线路的费用（但这个收费标准可能不止一种，例如车票跟机票一般不是一个价格）。
Z 省为了鼓励大家在省内多逛逛，推出了旅游金计划：在 i 号城市可以用 1 元现金兑换 ai元旅游金（只要现金足够，可以无限次兑换）。城市间的交通即可以使用现金支付路费，也可以用旅游金支付。具体来说，当通过第 j 条旅行线路时，可以用 cj元现金或 dj元旅游金支付路费。注意： 每次只能选择一种支付方式，不可同时使用现金和旅游金混合支付。但对于不同的线路，旅客可以自由选择不同的支付方式。
森森决定从 1 号城市出发，到 n 号城市去。他打算在出发前准备一些现金，并在途中的某个城市将剩余现金 全部 换成旅游金后继续旅游，直到到达 n 号城市为止。当然，他也可以选择在 1 号城市就兑换旅游金，或全部使用现金完成旅程。
Z 省政府会根据每个城市参与活动的情况调整汇率（即调整在某个城市 1 元现金能换多少旅游金）。现在你需要帮助森森计算一下，在每次调整之后最少需要携带多少现金才能完成他的旅程。
输入格式:
输入在第一行给出三个整数 n，m 与 q（1≤n≤105 1≤m≤2×105,1≤q≤105），依次表示城市的数量、旅行线路的数量以及汇率调整的次数。
接下来 m 行，每行给出四个整数 u，v，c 与 d（1≤u,v≤n，1≤c,d≤109），表示一条从 u 号城市通向 v 号城市的有向旅行线路。每次通过该线路需要支付 c 元现金或 d 元旅游金。数字间以空格分隔。输入保证从 1 号城市出发，一定可以通过若干条线路到达 n 号城市，但两城市间的旅行线路可能不止一条，对应不同的收费标准；也允许在城市内部游玩（即 u 和 v 相同）。
接下来的一行输入 n 个整数 a1 ,a2,⋯,an（1≤ai≤109），其中 ai 表示一开始在 i 号城市能用 1 元现金兑换 ai个旅游金。数字间以空格分隔。
接下来 q 行描述汇率的调整。第 i 行输入两个整数 xi与 ai（1≤xi ≤n,1≤ai ≤109），表示第 i 次汇率调整后，xi号城市能用 1 元现金兑换ai个旅游金，而其它城市旅游金汇率不变。请注意：每次汇率调整都是在上一次汇率调整的基础上进行的。
输出格式:
对每一次汇率调整，在对应的一行中输出调整后森森至少需要准备多少现金，才能按他的计划从 1 号城市旅行到 n 号城市。
再次提醒：如果森森决定在途中的某个城市兑换旅游金，那么他必须将剩余现金全部、一次性兑换，剩下的旅途将完全使用旅游金支付。
输入样例:
6 11 3 1 2 3 5 1 3 8 4 2 4 4 6 3 1 8 6 1 3 10 8 2 3 2 8 3 4 5 3 3 5 10 7 3 3 2 3 4 6 10 12 5 6 10 6 3 4 5 2 5 100 1 2 2 1 1 17
输出样例:
8 8 1
样例解释:
对于第一次汇率调整，森森可以沿着 1→2→4→6 的线路旅行，并在 2 号城市兑换旅游金；
对于第二次汇率调整，森森可以沿着 1→2→3→4→6 的线路旅行，并在 3 号城市兑换旅游金；
对于第三次汇率调整，森森可以沿着 1→3→5→6 的线路旅行，并在 1 号城市兑换旅游金。
思路：正向求一遍到每个城市现金的最小花费，反向求一遍到每个城市旅游金的最小花费，然后把花费换算现金，求出最小的花费的现金
#include <bits/stdc++.h> #define x first; #define y second using namespace std; typedef long long LL; typedef pair<LL,int> PII; const int N = 2e5,M = 4e5; const LL inf = 0x3f3f3f3f3f3f3f3f; int n,m,q; int h1[M],h2[M],ne[M],e[M],w[M],idx; LL dist1[M],dist2[M]; bool st[M]; int radio[M]; void add(int h[],int a,int b,int c) // 邻接表 { e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++; } void dijkstra(int h[],LL dist[],int u) // 求最短路 { memset(dist,inf,sizeof dist1); memset(st,0,sizeof st); dist[u] = 0; priority_queue<PII,vector<PII>,greater<PII> >heap; heap.push({0,u}); while(heap.size() > 0) { auto t = heap.top(); heap.pop(); if(st[t.y]) continue; st[t.y] = 1; for(int i=h[t.y];i!=-1;i=ne[i]) { int j = e[i]; if(dist[j] > dist[t.y] + w[i]) { dist[j] = dist[t.y] + w[i]; heap.push({dist[j],j}); } } } } int main() { scanf("%d%d%d",&n,&m,&q); memset(h1,-1,sizeof h1); memset(h2,-1,sizeof h2); while(m -- ) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); add(h1,a,b,c); add(h2,b,a,d); } dijkstra(h1,dist1,1); dijkstra(h2,dist2,n); for(int i=1;i<=n;i++) scanf("%d",&radio[i]); multiset<LL>S; for(int i=1;i<=n;i++) { if(dist1[i] != inf && dist2[i] != inf) // 避免把不存在的路径加进来 S.insert(dist1[i] + (dist2[i] + radio[i] - 1) / radio[i]); } while(q -- ) { int a,b; scanf("%d%d",&a,&b); if(dist1[a] != inf && dist2[a] != inf) { S.erase(S.find(dist1[a] + (dist2[a] + radio[a] - 1) / radio[a])); radio[a] = b; // 汇率调整 S.insert(dist1[a] + (dist2[a] + radio[a] - 1) / radio[a]); } printf("%lld\n",*S.begin()); // 输出最小花费的方案 } return 0; }
7: AcWing 1475. 紧急情况(PAT甲级真题1003)
作为城市的紧急救援团队负责人，你将获得一张你所在国家的特殊地图。
该地图显示了一些通过道路连接的分散城市，道路是双向的。
地图上标出了每个城市的救援队数量以及每对城市之间的每条道路的长度。
当其他城市发出紧急求援信息时，你的工作是尽快带领你的士兵前往该地点，同时，在途中尽可能多地调动救援帮手。
输入格式
第一行包含四个整数 N，表示城市数量（城市编号从 0 到 N−1），M 表示道路数量，C1 表示你当前所在的城市编号，C2 表示发出紧急求援信息的城市编号。
第二行包含 N 个整数，其中第 i 个整数表示城市 i 的救援队数量。
接下来 M 行，每行包含三个整数 c1,c2,Li，表示城市 c1 和城市 c2 之间存在一条道路相连，道路长度为 Li。
数据保证 C1 和 C2 之间至少存在一条路径相连。
输出格式
共一行，两个整数，第一个整数表示 C1 和 C2 之间最短路的数量，第二个整数表示走最短路的情况下，能聚集到的救援队最大数量。
数据范围
2≤N≤500,
1≤M≤600,
1≤Li≤200,
每个城市包含的救援人员数量不超过 200。
输入样例：
5 6 0 2 1 2 1 5 3 0 1 1 0 2 2 0 3 1 1 2 1 2 4 1 3 4 1
输出样例：
2 4
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 510,inf = 0x3f3f3f3f; int n,m,c1,c2; int g[N][N]; int dist[N],num[N],sum[N],cnt[N]; bool st[N]; void dijkstra(int u) { memset(dist,inf,sizeof dist); dist[u] = 0; cnt[u] = 1; for(int i=0;i<n;i++) { int t = -1; for(int j=0;j<n;j++) if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true; for(int j=0;j<n;j++) { if(dist[j] > dist[t] + g[t][j]) { dist[j] = dist[t] + g[t][j]; cnt[j] = cnt[t]; sum[j] = sum[t] + num[j]; } else if(dist[j] == dist[t] + g[t][j]) { cnt[j] += cnt[t]; if(sum[j] < sum[t] + num[j]) { sum[j] = sum[t] + num[j]; } } } } } int main() { cin >> n >> m >> c1 >> c2; memset(g,inf,sizeof g); for(int i=0;i<n;i++) cin >> num[i],sum[i] = num[i]; while (m -- ) { int a,b,l; cin >> a >> b >> l; g[a][b] = g[b][a] = min(g[a][b],l); } dijkstra(c1); cout << cnt[c2] << ' ' << sum[c2]; return 0; }
