Heavy Transportation---poj1797

求（Dijkstra算法，求每条路径上的最小值 的最大值）和青蛙的那题类似；

 

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#define INF 0xfffffff
#define N 1100
using namespace std;

int n,m,dist[N],vis[N];
int maps[N][N];

void Init()
{
    int i,j;
    memset(vis,0,sizeof(vis));
    for(i=0;i<=n;i++)
    {
        dist[i]=0;
        for(j=0;j<=n;j++)
        {
            maps[i][j]=0;
        }
    }
}

void Dij(int Start,int End)
{
    int Max,index,i,j;
    dist[Start] = INF;
    for(i = 1; i <= n; i++)
    {
        index=-1;
        Max=0;
        for(j = 1; j <= n; j++)
        {
            if(vis[j] == 0  && Max < dist[j])
            {
                Max = dist[j];
                index = j;
            }
        }
        if(index == -1)break;
        vis[index] = 1;
        for(j = 1; j <= n; j++)
        {
            if(vis[j] == 0&&dist[j] < min(dist[index],maps[index][j]))

                dist[j] = min(dist[index],maps[index][j]);
        }
    }
}

int main()
{
    int T,t=1,a,b,c;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);

        Init();

        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);

            maps[a][b] = maps[b][a] = max(maps[a][b],c);
        }
        Dij(1,n);

        printf("Scenario #%d:
%d

",t++,dist[n]);
    }
    return 0;
}

 下面是相当于求最大生成树的方法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <queue>
#include <algorithm>
using namespace std;
#define N 1210
#define INF 0xfffffff

int dist[N], maps[N][N], vis[N], n, ans;
void Dij(int s, int e)
{
    for(int i=1; i<=n; i++)
        dist[i] = maps[s][i];
    for(int i=1; i<=n; i++)
    {
        int Max = 0, Index = -1;
        for(int j=1; j<=n; j++)
        {
            if(vis[j]==0 && Max<dist[j])
            {
                Max = dist[j];
                Index=j;
            }
        }
        if(Index == -1)break;

        vis[Index]=1;

        ans=min(ans, dist[Index]);

        if(Index==n)return ;

        for(int j=1; j<=n; j++)
        {
            if(vis[j]==0 && dist[j]<maps[Index][j])
                dist[j] = maps[Index][j];
        }
    }
}
int main()
{
    int T, t=1, m, a, c, b;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        memset(vis, 0, sizeof(vis));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                maps[i][j]=0;
            dist[i]=maps[i][i]=0;
        }
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            maps[a][b] = maps[b][a] = max(maps[a][b], c);
        }
        ans = INF;
        Dij(1, n);
        printf("Scenario #%d:
", t++);
        printf("%d

", ans);
    }
    return 0;
}