POJ - 1797 Heavy Transportation（dijkstra）

题目链接: [Heavy Transportation]

大致题意:

从点1到点n，很多条路径，每条路径都有一个最小的权值，求这些最小的权值里的最大值

解题思路:

dis数组的含义: dis[i] 代表1到i点的所有路径最小的权值（一条路径只有一个） 最大的一个（就是把每一条路径的最小权值放在一起，找到最大的一个）

正常dijkstra思路是找到一条最小权值的边tmp，从1到n遍历，看是否存在一条包含tmp的路径，使得该路径权值比dis[i]更短，然后更新。

然后这道题要求找每条路径中最小边权，在这所有边权中找到一个最大值，所以思路是找到一条最大权值的边tmp，从1到n遍历，前提是存在并找到一条从1到i的路径，然后找到这条路径中边权最小的一条边，与dis[i]（第一次遍历，我们认为dis[i]要么是题目中给出一条1到i的路径，要么是题目没给但我们初始化使得dis[i]=0）进行比较，更新最大值

AC代码:

#include<iostream>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N = 1010;
const int INF = 0x3f3f3f3f;
int mp[N][N];
int n, m;
int dis[N];
int vis[N];
void dijkstra() {
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; ++i)dis[i] = mp[1][i];
for (int i = 1; i <= n; ++i) {
int tmp = 0; int index = -1;
for (int j = 1; j <= n; ++j) {
if (!vis[j] && dis[j] > tmp) {
tmp = dis[j]; index = j;
}
}
if (index == -1)break;
vis[index] = 1;
for (int j = 1; j <= n; ++j) {
if (!vis[j] && dis[j] < min(mp[index][j], tmp))
dis[j] = min(mp[index][j], tmp);
}
}
}
int main(void)
{
int t; scanf("%d", &t);
int p = 1;
for(int j=1;j<=t;++j){
memset(mp, 0, sizeof mp);
scanf("%d%d", &n, &m);
while (m--) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
mp[u][v] = mp[v][u] = w; //无向图
}
dijkstra();
printf("Scenario #%d:n%dnn", j, dis[n]);
}
return 0;
}

END

最后

以上就是疯狂白猫为你收集整理的POJ - 1797 Heavy Transportation（dijkstra）的全部内容，希望文章能够帮你解决POJ - 1797 Heavy Transportation（dijkstra）所遇到的程序开发问题。

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