POJ 1797 Heavy Transportation Dijstr最短絡変形
1318 ワード
この問題は私の前のブログPOJ 2253と言っても兄弟ではない兄弟のテーマです!
POJ 2253は最小を求める最大距離である.
本題は最大の最小距離を求めることです.今回は完全に自分で書いたので、1 A、Dijstraに対する理解がまた少し進歩しました.
POJ 2253は最小を求める最大距離である.
本題は最大の最小距離を求めることです.今回は完全に自分で書いたので、1 A、Dijstraに対する理解がまた少し進歩しました.
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int mp[1005][1005],vis[1005],lowc[1000005];
int m,n;
int Dijstra()
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++) lowc[i]=mp[1][i];
lowc[1]=1000000;
for(int j=1;j<=n;j++)
{
int maxc=0,p=-1;
for(int i=1;i<=n;i++)
if(!vis[i]&&lowc[i]>maxc)
{
maxc=lowc[i];
p=i;
}
if(p==n) return maxc;
vis[p]=1;
for(int i=1;i<=n;i++)
if(!vis[i] && lowc[i]<min(lowc[p],mp[p][i]))
lowc[i]=min(lowc[p],mp[p][i]);
}
return lowc[n];
}
int main()
{
int t,u,v,w,cas=1;;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(mp,0,sizeof(mp));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
mp[u][v]=mp[v][u]=w;
}
printf("Scenario #%d:
%d
",cas++,Dijstra());
}
return 0;
}