HDU杭电1874-畅通工程续（dijkstra算法和Floyd算法）

题目地址：http://acm.hdu.edu.cn/showPRoblem.php?pid=1874

/**************

此题是典型的最短路径问题，以下dijkstra代码（效率高）和Floyd代码（费时）。

算法学习：http://blog.csdn.net/winter2121/article/details/55805391

/************************************************************************************

dijkstra：

#include<stdio.h>int map[205][205];int vis[205],len[205];const int MAX=0xfffffff;int main(){    int N,M;    int a,b,x;    int s,t;    while(scanf("%d%d",&N,&M)!=EOF)    {        for(int i=0;i<N;i++)        {            vis[i]=0;   //所有城市标记为未访问            len[i]=MAX;  //所有路径标记为无穷大         }                        for(int i=0;i<N;i++)//数组初始化         for(int j=0;j<N;j++)        {            map[i][j]= i==j ? 0:MAX;        }                    for(int i=0;i<M;i++)//数据输入         {            scanf("%d%d%d",&a,&b,&x);            if(map[a][b]>x)            {                map[a][b]=map[b][a]=x;            }                        }        scanf("%d%d",&s,&t);                //dijkstra算法        for(int i=0;i<N;i++)        {            len[i]=map[s][i];        }        vis[s]=1;//出发城市标记为已访问         while(1)        {            int min=MAX;            int k=-1;            for(int i=0;i<N;i++)//寻找下一个城市（路最短）            {                if(vis[i]==0&&len[i]<min)                {                    min=len[i];                    k=i;                }             }             if(k<0) break;//所有城市都被标记完了            vis[k]=1;            for(int i=0;i<N;i++)            {                if(vis[i]==0&&len[i]>len[k]+map[k][i])                {                    len[i]=len[k]+map[k][i];                }            }        }                        printf("%d/n",len[t]==MAX ? -1 : len[t] );    }    return 0;}
Floyd：
注意城市i到i时间为0，其他为无穷大
#include<stdio.h>int map[205][205];const int MAX=0xfffffff;int main(){    int N,M;    int a,b,x;    int s,t;    while(scanf("%d%d",&N,&M)!=EOF)    {        for(int i=0;i<N;i++)//数组初始化         for(int j=0;j<N;j++)        {            map[i][j]= i==j?0:MAX;        }                            for(int i=0;i<M;i++)//数据输入         {            scanf("%d%d%d",&a,&b,&x);            if(map[a][b]>x)                map[a][b]=map[b][a]=x;        }        scanf("%d%d",&s,&t);                //floyd算法        for(int k=0;k<N;k++)//中转城市k         for(int i=0;i<N;i++)//起点城市         for(int j=0;j<N;j++)//终点城市         {            if(map[i][j]>map[i][k]+map[k][j])                map[i][j]=map[i][k]+map[k][j];        }                 printf("%d/n",map[s][t]==MAX ? -1:map[s][t] );    }    return 0;}