POJ.1797 Heavy Transportation (Dijkstra变形)

题意分析

  1. 给出n个点,m条边的城市网络,其中 x y d 代表由x到y(或由y到x)的公路所能承受的最大重量为d,求从1到n的所有通路中,所能经过的的最大重量的车为多少。
  2. 2.

代码总览

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#define nmax 1005
#define inf 1e8+7
using namespace std;
int t,n,m;
int mp[nmax][nmax];
int shortpath[nmax];
bool visit[nmax];
void dij(int s)
{
int cur = s;
memset(visit,0,sizeof(visit));
for(int i = 1;i<=n;++i){shortpath[i] = mp[cur][i];}
shortpath[cur] = 0;
visit[cur] = true;
for(int i = 1;i<=n-1 ;++i){
int minL = 0;
for(int j = 1;j<=n;++j){
if(!visit[j] && shortpath[j] != 0 && shortpath[j] >minL){
minL = shortpath[j];
cur = j;
}
}
visit[cur] = true;
for(int j = 1;j<=n;++j){
if(!visit[j]){
shortpath[j] = max(min(mp[cur][j],shortpath[cur]),shortpath[j]);
}
}
}
}
void init()
{
scanf("%d %d",&n,&m);
for(int i = 1;i<=n;++i)
for(int j = 1;j<=n;++j)
mp[i][j] = 0;
for(int i = 1;i<=m;++i){
int sta,end,dis;
scanf("%d %d %d",&sta,&end,&dis);
mp[sta][end] = mp[end][sta] = dis;
}
}
int main()
{
//freopen("in.txt","r",stdin);
int kase = 1;
scanf("%d",&t);
for(int i = 1;i<=t;++i){
init();
dij(1);
printf("Scenario #%d:\n",kase++);
printf("%d\n\n",shortpath[n]);
}
return 0;
}
04-18 18:06