学步园

#include <stdio.h>
#include <string.h>
#define M 1005
#define MAX 100000
int edge[M][M];

void dij(int n)
{
    int
mark[M],dis[M];
    int
i,count,k;
    count = n
-1;
   
memset(mark,0,sizeof(mark));
    for (i = 1;i
<= n;i ++)
       
dis[i] = edge[n][i];
    mark[n] =
1;
    while (count
--)
    {
       
int min = MAX;
       
for (i = 1;i <= n;i ++)
           
if (!mark[i]&&dis[i]
< min)
           
{
               
min = dis[i];
               
k = i;
           
}
       
mark[k] = 1;
       
for (i = 1;i <= n;i ++)
           
if (!mark[i]&&dis[i]
> dis[k] + edge[k][i])
               
dis[i] = dis[k] + edge[k][i];
    }

    printf
("%d\n",dis[1]);
}
int main ()
{
    int
t,n,v1,v2,w,i,j;
    scanf
("%d%d",&t,&n);
    for (i = 1;i
<= n;i ++)
       
for (j = 1;j <= n;j ++)
           
edge[i][j] = MAX;
    while (t
--)
    {
       
scanf
("%d%d%d",&v1,&v2,&w);

       
w = edge[v1][v2] > w?w:edge[v1][v2];
       
edge[v1][v2] = w;
       
edge[v2][v1] = w;
    }

    dij
(n);
    return
0;
}