Dijkstra算法
例题描述
小明是蓝桥王国的王子，今天是他登基之日。
在即将成为国王之前，老国王给他出了道题，他想要考验小明是否有能力管理国家。
题目的内容如下：
蓝桥王国一共有 N 个建筑和 M 条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为 1∼N 。（其中皇宫的编号为 11）
国王想让小明回答从皇宫到每个建筑的最短路径是多少，但紧张的小明此时已经无法思考，请你编写程序帮助小明回答国王的考核。
输入描述
输入第一行包含三个正整数 N,M。
第 2 到M+1 行每行包含三个正整数 u,v,w，表示 u→v 之间存在一条距离为 w 的路。
1≤N≤3×10^5，1≤m≤10^6，1≤ui,vi≤N，0≤wi≤10^9。
输出描述
输出仅一行，共 N 个数，分别表示从皇宫到编号为 1∼N 建筑的最短距离，两两之间用空格隔开。（如果无法到达则输出 −1）
样例输入
1. 3 3 2. 1 2 1 3. 1 3 5 4. 2 3 2
样例输出
0 1 3
1. #include<bits/stdc++.h> 2. using namespace std; 3. const long long INF = 0x3f3f3f3f3f3f3f3fLL; //这样定义INF的好处是: INF <= INF+x 4. const int NUM = 3e5+2; 5. struct edge{ 6. int from, to; long long w; 7. //边：起点，终点，权值。起点from并没有用到，e[i]的i就是from 8. edge(int a, int b,long long c){from=a; to=b; w=c;} 9. }; 10. vector<edge>e[NUM]; //用于存储图 11. struct s_node{ 12. int id; long long n_dis; //id：结点；n_dis：这个结点到起点的距离 13. s_node(int b,long long c){id=b; n_dis=c;} 14. bool operator < (const s_node & a) const 15. { return n_dis > a.n_dis;} 16. }; 17. int n,m; 18. int pre[NUM]; //记录前驱结点 19. void print_path(int s, int t) { //打印从s到t的最短路 20. if(s==t){ printf("%d ", s); return; } //打印起点 21. print_path(s, pre[t]); //先打印前一个点 22. printf("%d ", t); //后打印当前点。最后打印的是终点t 23. } 24. long long dis[NUM]; //记录所有结点到起点的距离 25. void dijkstra(){ 26. int s = 1; //起点s是1 27. bool done[NUM]; //done[i]=true表示到结点i的最短路径已经找到 28. for (int i=1;i<=n;i++) {dis[i]=INF; done[i]=false; } //初始化 29. dis[s]=0; //起点到自己的距离是0 30. priority_queue <s_node> Q; //优先队列，存结点信息 31. Q.push(s_node(s, dis[s])); //起点进队列 32. while (!Q.empty()) { 33. s_node u = Q.top(); //pop出距起点s距离最小的结点u 34. Q.pop(); 35. if(done[u.id]) //丢弃已经找到最短路径的结点。即集合A中的结点 36. continue; 37. done[u.id]= true; 38. for (int i=0; i<e[u.id].size(); i++) { //检查结点u的所有邻居 39. edge y = e[u.id][i]; //u.id的第i个邻居是y.to 40. if(done[y.to]) //丢弃已经找到最短路径的邻居结点 41. continue; 42. if (dis[y.to] > y.w + u.n_dis) { 43. dis[y.to] = y.w + u.n_dis; 44. Q.push(s_node(y.to, dis[y.to])); 45. //扩展新的邻居，放到优先队列中 46. pre[y.to]=u.id; //如果有需要，记录路径 47. } 48. } 49. } 50. // print_path(s,n); //如果有需要，打印路径: 起点1，终点n 51. } 52. int main(){ 53. scanf("%d%d",&n,&m); 54. for (int i=1;i<=n;i++) 55. e[i].clear(); 56. while (m--) { 57. int u,v,w; 58. scanf("%d%d%lld",&u,&v,&w); 59. e[u].push_back(edge(u,v,w)); 60. // e[v].push_back(edge(v,u,w)); //本题是单向道路 61. } 62. dijkstra(); 63. for(int i=1;i<=n;i++){ 64. if(dis[i]>=INF) cout<<"-1 "; 65. else printf("%lld ", dis[i]); 66. } 67. }
Floyd算法
例题描述
小明喜欢观景，于是今天他来到了蓝桥公园。
已知公园有 N 个景点，景点和景点之间一共有 M 条道路。小明有 Q 个观景计划，每个计划包含一个起点 st 和一个终点 ed，表示他想从 st 去到 ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？
输入描述
输入第一行包含三个正整数 N,M,Q
第 2 到 M+1 行每行包含三个正整数 u,v,w，表示u↔v 之间存在一条距离为 w 的路。
第 M+2 到 M+Q−1 行每行包含两个正整数 st,ed，其含义如题所述。
1≤N≤400，1≤M≤（N×(N−1)/2，Q≤10^3，1≤u,v,st,ed≤n，1≤w≤10^9
输出描述
输出共 Q 行，对应输入数据中的查询。
若无法从 st 到达 ed 则输出 -1。
样例输入
1. 3 3 3 2. 1 2 1 3. 1 3 5 4. 2 3 2 5. 1 2 6. 1 3 7. 2 3
样例输出
1. 1 2. 3 3. 2
1. #include <bits/stdc++.h> 2. using namespace std; 3. const long long INF = 0x3f3f3f3f3f3f3f3fLL; //这样定义INF的好处是: INF <= INF+x 4. const int N = 405; 5. long long dp[N][N]; 6. int n,m,q; 7. void input(){ 8. // for(int i = 1; i <= n; i++) 9. // for(int j = 1; j <= n; j++) 10. // dp[i][j] = INF; 11. memset(dp,0x3f,sizeof(dp)); //两种初始化方法 12. for(int i = 1; i <= m; i++){ 13. int u,v;long long w; 14. cin >> u >> v >> w; 15. dp[u][v]=dp[v][u]=min(dp[u][v] , w); //防止有重边 16. } 17. } 18. void floyd(){ 19. for(int k = 1; k <= n; k++) 20. for(int i = 1; i <= n; i++) 21. for(int j = 1; j <= n; j++) 22. dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j]); 23. } 24. void output(){ 25. int s, t; 26. while(q--){ 27. cin >> s >>t; 28. if(dp[s][t]==INF) cout << "-1" <<endl; 29. else if(s==t) cout << "0" <<endl; //如果不这样，dp[i][i]不等于0 30. else cout <<dp[s][t]<<endl; 31. } 32. } 33. int main(){ 34. cin >> n>> m >> q; 35. input(); 36. floyd(); 37. output(); 38. return 0; 39. }
