HDOJ2544 ( 最短路 ) 【最短路径Dijkstra】

Problem : 2544 ( 最短路 )     Judge Status : Accepted
RunId : 6003616    Language : C++    Author : qq1203456195
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 0x3f3f3f3f
#define N 105
int cls[N],n,m;
int map[N][N];
int vis[N];
void Dijkstra(int v)
{
    int i,j,min,nxt;
    for(i=1;i<=n;i++)    cls[i]=map[v][i];
    memset(vis,0,sizeof(vis));
    vis[v]=1;
    for (i=1;i<n;i++)
    {
        min=MAX;
        nxt=v;
        for (j=1;j<=n;j++)
        {
            if(!vis[j]&&cls[j]<min)
            {
                nxt=j;
                min=cls[j];
            }
        }
        vis[nxt]=1;
        for (j=1;j<=n;j++)
        {
            if(!vis[j]&&map[nxt][j]<MAX&&(min+map[nxt][j])<cls[j])
                cls[j]=cls[nxt]+map[nxt][j];
        }
    }
}
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&m),m||n)
    {
        memset(map,MAX,sizeof(map));
        while (m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(map[a][b]>c)    map[a][b]=map[b][a]=c;
        }
        Dijkstra(1);
        printf("%d\n",cls[n]);
    }
    return 0;
}