poj1797 最短路变形

题目大意：求第1个点到第n个点的路径中所有的边所能承受最小重力的最大值

思路： 刚开始一想没有思路然后想到用Floyd不断更新到每个点的最大值得最小值，TLE一发后想到这样做可能是错的，不仅仅是时间复杂度太高，更新过程中还要记录所有边的最小值，所以就想到了Dijkstra算法，不断更新距离已知集合的最大值不断把最大值得点加进去，中间记录答案

网上见有的人说最大生成树，确实有道理，prim算法和dijkstra算法只是更新的时候不一样而已

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000+5;
int f[maxn][maxn];
int dis[maxn], vis[maxn];
int n, m;
void dijkstra()
{
for (int i = 1; i <= n; i++) dis[i] = f[1][i];
memset(vis, 0, sizeof(vis));
vis[1] = 1;
dis[1] = 0;
int ans = 0x7f7f7f7f;
for (int i = 1; i <= n; i++)
{
int mmax = 0, x = 0;
for (int j = 1; j <= n; j++)
{
if (!vis[j] && mmax < dis[j])
{
mmax = dis[j];
x = j;
}
}
if(ans > mmax) ans = mmax;
if (x == n) break;
vis[x] = 1;
for (int j = 1; j <= n; j++)
{
if(!vis[j] && dis[j] < f[x][j])
dis[j] = f[x][j];
}
}
cout << ans << endl;
}
int main()
{
//freopen("in", "r", stdin);
int t;
int kcase = 0;
cin >> t;
while (t--)
{
memset(f, 0, sizeof(f));
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
f[x][y] = f[y][x] = z;
}
printf("Scenario #%d:n", ++kcase);
dijkstra();
cout << endl;
}
return 0;
}

最后

以上就是阳光大树为你收集整理的poj1797 最短路变形的全部内容，希望文章能够帮你解决poj1797 最短路变形所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。