最短路

hdoj2544

题目大意：给出两点和两点之间的时间代价，求出从起点到终点的最小时间 

解决：与hdoj 1874一模一样，地杰斯特拉算法求距离

#include <iostream>
using namespace std;
int n;
#define N 100
#define MAX 0x3f3f3f3f
int cost[N+10][N+10];
int vis[N+10];
int dist[N+10];
void init()
{
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      cost[i][j]=MAX;
}
void dijikstra()
{
    int v0=1;
    for(int i=1;i<=n;i++)
    {
        vis[i]=false;
        dist[i]=cost[v0][i];
    }
    vis[v0]=true;
    dist[v0]=0;//就算是v0到v0也能保证输出正确结果
    for(int i=1;i<n;i++)
    {
        int min=MAX;
        for(int j=2;j<=n;j++)
        {
            if(!vis[j] && dist[j]<min){min=dist[j];v0=j;}
        }
        vis[v0]=true;
        for(int j=2;j<=n;j++)
        if(!vis[j] && min+cost[v0][j]<dist[j])dist[j]=min+cost[v0][j];
    }
}
int main()
{
    int m;
    while(cin>>n>>m,n||m)
    {
        int a,b,w;
        init();
        for(int i=0;i<m;i++)
        {
            cin>>a>>b>>w;
           //必须进行下边的判断，否则结果错误，因为有重复的边输入
            if(w<cost[a][b]){cost[a][b]=cost[b][a]=w;}
        }
        dijikstra();
        cout<<dist[n]<<endl;
    }
 //   system("pause");
    return 0;
}