[kuangbin带你飞] 题单 最短路问题 + 并查集问题模板题及简单题 https://blog.csdn.net/m0_46272108/article/details/108923142
题意： N个点，M条边，每条边有权值。求一条1号点到N号点的路径，要求使得路径中的边权最小值最大。 题解： 最短路问题 Dijkstra算法 详看代码，有注释！！！
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ll long long //#define int ll #define INF 0x3f3f3f3f using namespace std; int read() { int w = 1, s = 0; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * w; //最大公约数 }int gcd(int x,int y) { if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后 //递归终止条件千万不要漏了，辗转相除法 return x % y ? gcd(y, x % y) : y; } int lcm(int x,int y)//计算x和y的最小公倍数 { return x * y / gcd(x, y);//使用公式 } //------------------------ 以上是我常用模板与刷题几乎无关 ------------------------// const int N = 1010; int Map[N][N];//用邻接矩阵来存 int dist[N]; bool st[N];//用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新 int n, m; void dijstra() { memset (st, 0, sizeof(st)); for (int i = 1; i <= n; ++i) { dist[i] = Map[1][i]; } for (int i = 1; i <= n; ++i) { int minn = 0; int k; //这里的j代表的是从1号点开始 for (int j = 1; j <= n; ++j) { if (dist[j] > minn && !st[j]){ minn = dist[j]; k = j; } } //依次更新每个点所到相邻的点路径值 st[k] = true; for (int j = 1; j <= n; ++j) { dist[j] = max(dist[j], min(dist[k], Map[k][j])); } } } int main() { int cnt = 0; int t = read(); while(t--) { n = read(), m = read(); memset(Map, 0, sizeof(Map));//初始化 for (int i = 1; i <= m; ++i) { int start = read(); int end = read(); int val = read(); //如果发生重边的情况则保留最短的一条边 if (val) { Map[start][end] = val; Map[end][start] = val; } } dijstra(); printf("Scenario #%d:\n", ++cnt); printf("%d\n\n", dist[n]); } return 0; }