POJ--1797--Heavy Transportation (最短路)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

#define N 1100
#define INF 0x3f3f3f3f3f

int n, m, dist[N], G[N][N], v[N];

int DIST(int S, int E)
{
    dist[1]=0;
    v[1]=1;

    for(int i=1; i<=n; i++)
        dist[i] = G[1][i];

    for(int i=1; i<=n; i++)
    {
        int index=-1, MAX=-1;

        for(int j=1; j<=n; j++)
        {
            if(v[j]==0 && dist[j]>MAX)
            {
                index = j, MAX = dist[j];
            }
        }
        v[index]=1;

        for(int j=1; j<=n; j++)
        {
            if(v[j]==0)
            {
                int tmp = min(dist[index], G[index][j]);
                if(tmp>dist[j])
                    dist[j]=tmp;
            }
        }
    }
    return dist[E];
}

int main()
{
    int t, k=1;

    scanf("%d", &t);

    while(t--)
    {
        int a, b, w, i;
        scanf("%d%d", &n, &m);

        memset(v, 0, sizeof(v));
        memset(G, -1, sizeof(G));

        for(i=1; i<=m; i++)
        {
            scanf("%d%d%d", &a, &b, &w);
            G[a][b]=G[b][a]=max(G[a][b], w);
        }

        int ans = DIST(1, n);

        printf("Scenario #%d:\n", k++);
        printf("%d\n\n", ans);
    }
    return 0;
}