学步园

注意从0开始，计算时应计算dis[y],y是终点，如果防止错，所有的输入可以加上1，表示从1开始

#include<stdio.h>
#include<string.h>
#define data 1000000
int map[1100][1100];
int dis[1100];
int vis[1100];
int main()
{
 int n,m,p,i,j;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
  memset(vis,0,sizeof(vis));
  for(i=0;i<=n;i++)
   for(j=0;j<=n;j++)
    map[i][j]=data;
  int a,b,t;
  for(i=1;i<=m;i++)
  {
   scanf("%d%d%d",&a,&b,&t);
   if(map[a][b]>t) map[a][b]=map[b][a]=t;
  }
  int x,y;
  scanf("%d%d",&x,&y);
  for(i=0;i<=n;i++)
   dis[i]=(i==x?0:data);
  for(i=0;i<=n;i++)
  {
   int x1,M=data;
   for(j=0;j<=n;j++)
    if(!vis[j]&&dis[j]<=M)
    {M=dis[j];x1=j;}
    vis[x1]=1;
    for(j=0;j<=n;j++)
     dis[j]=dis[j]<dis[x1]+map[x1][j]?dis[j]:dis[x1]+map[x1][j];
  }
  if(dis[y]!=data)
  printf("%d\n",dis[y]);
  else printf("-1\n");
 }
 return 0;
}

注意是无向图