专注 效率 记忆
预习 笔记 复习 做题

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
　
文章字体风格：
红色文字表示：重难点★✔
蓝色文字表示：思路以及想法★✔
　
如果大家觉得有帮助的话，感谢大家帮忙
点赞！收藏！转发！

本博客带大家一起学习，我们不图快，只求稳扎稳打。
由于我高三是在家自学的，经验教训告诉我，学习一定要长期积累，并且复习，所以我推出此系列。
只求每天坚持40分钟，一周学5天，复习2天
也就是一周学10道题
60天后我们就可以学完81道题，相信60天后，我们一定可以有扎实的代码基础！我们每天就40分钟，和我一起坚持下去吧！
qq群：878080619

三十一、最短路

1. 我想回家（北京大学考研机试题）

求城市1到所属阵营城市的最短路径，记录在dist1[]中
求城市2到所属阵营城市的最短路径，记录在dist2[]中
遍历所有边，边的两端的城市i、j分别属于阵营1、2, 该边的权重为w
那么本题可以等价于求解：
min(w+dist[i]+dist[j])

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N=610,M=20010,INF=0x3f3f3f3f;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int q[N],dist1[N],dist2[N];
bool st[N];
int team[N];void add(int a,int b,int c){e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}void spfa(int start,int dist[]){int hh=0,tt=1;q[0]=start;memset(dist,0x3f,sizeof dist1);dist[start]=0;while(hh!=tt){// 队头元素出队 int t=q[hh++];   if(hh==N) hh=0;  // 循环队列 st[t]=false;// 遍历该元素的所有邻接点 for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(team[j]!=start)continue; // 如果是不同阵营的则跳过 if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];  // 更新，入队 if(!st[j]){q[tt++]=j;if(tt==N) tt=0; // 循环队列 st[j]=true;}}}}
}
int main(){while(scanf("%d",&n),n){scanf("%d",&m);memset(h,-1,sizeof h),idx=0;while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c),add(b,a,c);   // 无向图，添加双向边 } for(int i=1;i<=n;i++) scanf("%d",&team[i]);  // 输入所属的团队 spfa(1,dist1);spfa(2,dist2);int res=INF;for(int i=0;i<idx;i++){int a=e[i^1],b=e[i];// 方向相反的一对边 if(team[a]==1 && team[b]==2) // 如果该边连接的两个城市属于不同阵营，则可以更新边 res=min(res,dist1[a]+w[i]+dist2[b]); }if(res==INF) puts("-1");else cout<<res<<endl; }return 0;
}

2. 最短路径

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110, MOD = 100000, INF = 0x3f3f3f3f;int n, m;
int p[N];
int d[N][N];int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m;for (int i = 0; i < n; i ++ ) p[i] = i;memset(d, 0x3f, sizeof d);for (int i = 0; i < n; i ++ ) d[i][i] = 0;for (int i = 0, len = 1; i < m; i ++, len = len * 2 % MOD){int a, b;cin >> a >> b;if (find(a) != find(b)){p[find(a)] = find(b);d[a][b] = d[b][a] = len;}}for (int k = 0; k < n; k ++ )for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);for (int i = 1; i < n; i ++ )if (d[0][i] == INF) puts("-1");else cout << d[0][i] % MOD << endl;return 0;
}

3. 最短路径

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 55, M = N * N / 2, INF = 0x3f3f3f3f;int n, m, Q;
int g[N][N], d[N][N];
struct Edge
{int a, b;
}e[M];void floyd()
{memcpy(d, g, sizeof d);for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main()
{int T;cin >> T;while (T -- ){cin >> n >> m >> Q;memset(g, 0x3f, sizeof g);for (int i = 0; i < n; i ++ ) g[i][i] = 0;for (int i = 1; i <= m; i ++ ){int a, b, c;cin >> a >> b >> c;e[i] = {a, b};g[a][b] = g[b][a] = c;}floyd();printf("%d\n", d[1][n]);while (Q -- ){int t;cin >> t;int a = e[t].a, b = e[t].b;g[a][b] = g[b][a] = INF;}floyd();if (d[1][n] == INF) puts("-1");else cout << d[1][n] << endl;}return 0;
}