最短路-HDU2544-dijkstra模板题

/*
最短路 
*/
#include <stdio.h>
#define N 110
int map[N][N];
int n,m;
int dist[N];
int flag[N];
 
void find()
{
    int i,j,l;
    //将到达其他点的最短路径初始化 
    for(i=1;i<=n;i++) dist[i]=map[n][i];
    dist[n]=0;//n点到达n点的距离是0；
    flag[n]=1; 
    
    //一共需要找n-1个点的最短距离 
    for(l=1;l<n;l++){
        int k=-1;//k存储当前n点到达其他点的最短距离 
        int maxv=0x3f3f3f3f;//设置最大值 
        for(i=1;i<=n;i++){
            //如果当前点还没找过，且小于之前找过的最小值 
            if(flag[i]==0 && maxv>dist[i]){
                //则将k赋值，表示找到的最小的点 
                k=i;
                maxv=dist[i];
            } 
        } 
        
        //如果k==-1.则表示找了一圈，已经没有符合条件的最短的路了 
        if(k==-1){
            break;//直接退出 
        } 
        
        flag[k]=1;//找到的最短路标记一下 
        for(i=1;i<=n;i++){
            if(!flag[i] && maxv+map[k][i]<dist[i]){
                dist[i]=maxv+map[k][i];
            }
        } 
    } 
}

int main()
{
    int i,j;
    int a,b,c;
    while(scanf("%d%d",&n,&m)&&(n+m)){
        for(i=1;i<=n;i++){
            flag[i]=0;
            for(j=1;j<=n;j++){
                map[i][j]=0x3f3f3f3f;
            }
        } 
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            if(map[a][b]>c){
                map[a][b]=c;
                map[b][a]=c;
            }
        }
        find();
        printf("%d\n",dist[1]);
    }
    return 0; 
}