POJ 1797 Heavy Transportation Dijstr最短絡変形

1318 ワード

この問題は私の前のブログPOJ 2253と言っても兄弟ではない兄弟のテーマです!
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; }