本文主要是介绍POJ 1797 图论 Dijkstra，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
题意 求起点到终点 的 一个路径 使路径上最短边最长
性质：我们将 满足题意的从起点到点N的路径 记为Path（N）
在Path(N) 上 N 的前一个节点 为pre
那么在Path（N）上从起点到pre的路径 就是 Path（pre ）
否则我们可以将Path（pre）替换这条路径 Ｐａｔｈ（Ｎ）上的最短边只会更长
代码：
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#define sf scanf
#define pf printf
#define pow2(i) ( (i) * (i) )
using namespace std;
const int maxn = 1005;
const int INF = 0x3f3f3f3f;
int Adj[maxn][maxn];
int vis[maxn];
int dis[maxn];
int n,m;bool read(){sf("%d %d",&n,&m);memset(Adj,0x3f,sizeof(Adj));for(int i = 0;i < m;++i){int u,v,w;sf("%d%d%d",&u,&v,&w);Adj[u][v] = Adj[v][u] = w;}return n;
}int dijkstra(){for(int i = 0;i <= n;++i){vis[i] = 0;dis[i] = INF;Adj[i][i] = 0;}dis[1] = 0;vis[1] = 1;for(int i = 1;i <= n;++i){dis[i] = Adj[1][i];}for(int i = 1;i < n;++i){int lable = -1;int temp = -1;for(int j = 1;j <= n;++j){if(!vis[j] && dis[j] != INF && temp < dis[j]){temp = dis[lable = j];}}if(lable == -1) break;vis[lable] = 1;if(lable == n){return dis[n];}for(int j = 1;j <= n;++j){if(!vis[j] && Adj[lable][j] != INF){if(dis[j] == INF) dis[j] = min( dis[lable],Adj[lable][j] );else dis[j] = max(dis[j],min( dis[lable],Adj[lable][j] ) );}}}return dis[n];
}int main(){int Case;sf("%d",&Case);while(Case--){read();static int T = 0;pf("Scenario #%d:\n",++T);pf("%d\n",dijkstra());if(Case) pf("\n");}return 0;
}
这篇关于POJ 1797 图论 Dijkstra的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
