最短路

题目：

题解：

模板题

#include <bits/stdc++.h>
using namespace std;
int pos[105][105];
int dis[105];
int vis[105];
int inf=0x3f3f3f3f;
int n,m;
void dij()
{
  memset(dis,inf,sizeof(dis));
  dis[1]=0;
  for(int i=1;i<=n;i++)
  {
    int t=-1;
    for(int j=1;j<=n;j++)
    {
      if((t==-1||dis[j]<dis[t])&&!vis[j]) t=j;
    }
    vis[t]=1;
    for(int j=1;j<=n;j++)
    {
      dis[j]=min(dis[j],dis[t]+pos[t][j]);
    }
  }
}
int main()
{
  while(cin>>n>>m)
  {
    if(n==0&&m==0) break;
    memset(vis,0,sizeof(vis));
    memset(pos,inf,sizeof(pos));
    while(m--)
    {
      int a,b,c;
      cin>>a>>b>>c;
      pos[a][b]=pos[b][a]=min(pos[a][b],c);
    }
    dij();
    cout<<dis[n]<<endl;
  }
  return 0;
}