poj 1797 Heavy Transportation（最短路变种2，连通图的最小边）

题目

改动见下，请自行画图理解

具体细节也请看下面的代码：

 这个花了300多ms

#define  _CRT_SECURE_NO_WARNINGS

#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

const int MAXN=1010;  

#define typec int  
const typec INF=200000000;//防止后面溢出，这个不能太大  
bool vis[MAXN];  
typec cost[MAXN][MAXN];
typec lowcost[MAXN];
void Dijkstra(int n,int beg)  //连通图的最小边——最短路变种2，恰好和poj 2253 相反
{  
    for(int i=1;i<=n;i++)
    {
        lowcost[i]=cost[beg][i];vis[i]=false;//因为初始化都在这里了，所以后面的对起点的初始化可以省去
    }
    for(int i=1;i<=n;i++)
    {
        typec temp=-1;//此处改动
        int k=-1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&lowcost[j]>temp)//此处改动
            {
                temp=lowcost[j];
                k=j;
            }
        }
        vis[k]=true;
        for(int l=1;l<=n;l++)
        {
            if(!vis[l])
            {
                lowcost[l]=max(min(lowcost[k],cost[k][l]),lowcost[l]);//原来改动在这列，具体可画图求证感知
            }
        }
    }
}  

int main()
{
    int n,i,id=1,t,m,a,b,c;
    scanf("%d",&t);
    for(;id<=t;)
    {
        scanf("%d%d",&n,&m);//路口数和街道数不要反了！
        memset(cost,0,sizeof(cost));//初始化请注意，这里要都变为0，相当于无法运货，即载重量为0
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            cost[a][b]=cost[b][a]=c;//这里请注意
        }
        Dijkstra(n,1);
        printf("Scenario #%d:
%d

",id++,lowcost[n]);//居然在输出这里跪了
    }
    return 0;
}

在初始化时改一笔我觉得更容易理解，在此处也可以AC，但是时间多了，代码如下，花了400多ms

#define  _CRT_SECURE_NO_WARNINGS

#include<string.h>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;

const int MAXN=1010;  

#define typec int  
const typec INF=0x3f3f3f3f;//防止后面溢出，这个不能太大  
bool vis[MAXN];  
typec cost[MAXN][MAXN];
typec lowcost[MAXN];
void Dijkstra(int n,int beg)  //连通图的最小边——最短路变种2，恰好和poj 2253 相反
{  
    for(int i=1;i<=n;i++)
    {
        lowcost[i]=cost[beg][i];vis[i]=false;//因为初始化都在这里了，所以后面的对起点的初始化可以省去
    }
    for(int i=1;i<=n;i++)
    {
        typec temp=-1;//此处改动
        int k=-1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&lowcost[j]>temp)//此处改动
            {
                temp=lowcost[j];
                k=j;
            }
        }
        vis[k]=true;
        for(int l=1;l<=n;l++)
        {
            if(!vis[l])
            {
                lowcost[l]=max(min(lowcost[k],cost[k][l]),lowcost[l]);//原来改动在这列，具体可画图求证感知
            }
        }
    }
}  

int main()
{
    int n,i,id=1,t,m,a,b,c;
    scanf("%d",&t);
    for(;id<=t;)
    {
        scanf("%d%d",&n,&m);//路口数和街道数不要反了！
        memset(cost,0,sizeof(cost));//初始化请注意，这里要都变为0，相当于无法运货，即载重量为0
        
        for(i=1;i<=n;i++)
            cost[i][i]=INF;         //感觉加了这个更容易理解，因为是同一地方，载重量可以无限大
        
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            cost[a][b]=cost[b][a]=c;//这里请注意
        }
        Dijkstra(n,1);
        printf("Scenario #%d:
%d

",id++,lowcost[n]);//居然在输出这里跪了
    }
    return 0;
}