最短路径之数据结构

#include<string.h>
#include<stdlib.h>
#include <stdio.h>
using namespace std;
#define max 101
#define inf 99999
int n,m;
int map[max][max],vis[max],dist[max];
void Dij(int v){
    int i,j;
    int min;
    int flag;
    for(i=1;i<=n;i++){
        dist[i]=map[v][i];
        vis[i]=0;
    }
    dist[v]=0;
    vis[v]=1;
    for(i=0;i<n-1;i++){
        min=inf;
        flag=v;
        //找到这个与V点距离最近的点
        for(j=1;j<=n;j++){
            if(vis[j]==0&&dist[j]<min){
                flag=j;
                min=dist[j];
            }
        }
        vis[flag]=1;
        //更新dist数组
        for(int k=1;k<=n;k++){
            if(vis[k]==0&&map[flag][k]<inf&&dist[k]>dist[flag]+map[flag][k]){
                dist[k]=dist[flag]+map[flag][k];
            }
        }
    }
}
int main(){
    int i,j,a,b,c;
    while(scanf("%d %d",&n,&m)!=EOF){
            //进行初始化
        memset(vis,0,sizeof(vis));
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                if(i==j)
                    map[i][j]=0;
                else
                    map[i][j]=inf;
            }
        }
        //进行赋值
       for(i=0;i<m;i++){
            scanf("%d %d %d",&a,&b,&c);
            if(map[a][b]>c)
                map[a][b]=map[b][a]=c;
       }
       if(m==0)
            printf("0n");
       else{
            Dij(1);
            printf("%dn",dist[n]);
       }
    }
    return 0;
}