HDU

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544

#include <iostream>
#include <string.h>
#define MAX 10000005
#define N 10005
using namespace std;
/****************************************************************************************************************
                题意：找到规定起点终点的单源最短路经
                思路：
                1，dijkstra算法，看到一个大牛的blog，一张表格让我顿悟了
                2，dijkstra可以解决又向无向图，无向图给边赋较小的权值，有向图权值为1
                3，切记dijkstra不能解决负权图
****************************************************************************************************************/

int visit[N];       //用来判断是非在特殊路径集合点内
int dist[N];
int a[N][N];
int dijkstra(int n)
{
    for(int i = 1;i <= n;i ++)
        dist[i]=a[1][i];
    memset(visit,0,sizeof(visit));

    dist[1]=0;
    visit[1]=1;

    for(int i = 2;i <= n;i ++){
        int id=1,ansN=MAX;
        for(int j = 2;j <= n;j ++){
            if(!visit[j] && dist[j] < ansN){        //在S集合外找出最小路径点（即非特殊路径）
                ansN=dist[j];
                id=j;
            }
        }
        visit[id]=1;
        for(int j = 2;j <= n;j ++){     //以找到的最小路径点为最优解进行动态更新（非特殊路径集合点内遍历）
            if(!visit[j] && a[id][j] < MAX)
                dist[j]=min(dist[j],dist[id]+a[id][j]);
        }
    }
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n == 0 && m == 0)    break;
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= n;j ++)
                a[i][j]=MAX;
            dist[i]=MAX;
        }
        //memset(dist,MAX,sizeof(dist));

        int tempa,tempb,tempc;
        for(int i = 1;i <= m;i ++){
            cin>>tempa>>tempb>>tempc;
            if(tempc < a[tempa][tempb]){        //无向图，保存两次
                a[tempa][tempb]=tempc;
                a[tempb][tempa]=tempc;
            }
        }

        dijkstra(n);
        cout<<dist[n]<<endl;
    }
    return 0;
}