学步园

开始因为错写了m和n，runtime error了几次，用Dijkstra算法时，循环中应该是点的数目，也就是n，而不是m

注意该题是无向图
#include<iostream>
#include<cstring>
using namespace std;
#define data 100000000//注意取值，100000000才可以通过，其他的是running
int map[105][105];
int dis[105];
int vis[105];
int main()
{
 int n,m,i,j;
 while(1)
 {
  cin >> n >> m;
  if(n==0&&m==0) break;
  memset(vis,0,sizeof(vis));
  for(i=1;i<=n;i++)
   dis[i]=(i==n?0:data);
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    map[i][j]=data;
  int a,b,t;
  for(j=1;j<=m;j++)
  {
   cin >> a >> b >> t;
   if(map[a][b]>t)
    map[a][b]=map[b][a]=t;//无向图时初始化无论是a到b还是b到a都应该为t 
  }
  for(i=1;i<=n;i++)
  {
   int x,M=data;
   for(j=1;j<=n;j++)
    if(!vis[j]&&dis[j]<=M)
    { M=dis[j];x=j;}
    vis[x]=1;
   for(j=1;j<=n;j++)
    dis[j] = (dis[j]<dis[x]+map[x][j] ? dis[j] : dis[x]+map[x][j]);
  }
  printf("%d\n",dis[1]);
 }
 return 0;
}

 

 

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

3
2