hdu2544最短路——spfa

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#define inf 1000000
using namespace std;
struct node
{
int to,next,weight;
}city[10050];
int head[105];
int n,m,cur;
int mark[105];
int dis[105];
void init()
{
cur=0;
memset(city,0,sizeof(city));
for(int i=1;i<=n;i++)
{
mark[i]=0;
head[i]=-1;
dis[i]=inf;
}
}
void add(int A,int B,int C)
{
city[cur].to=B;
city[cur].weight=C;
city[cur].next=head[A];
head[A]=cur++;
}
void spfa()
{
queue<int>q;
int first,i;
dis[1]=0;
while(!q.empty()) q.pop();
q.push(1);
while(!q.empty())
{
first=q.front();
q.pop();
mark[first]=0;
for(i=head[first];i+1;i=city[i].next)
{
if(dis[first]+city[i].weight<dis[city[i].to])
{
dis[city[i].to]=dis[first]+city[i].weight;
if(mark[city[i].to]==0)
{
q.push(city[i].to);
mark[city[i].to]=1;
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0) break;
init();
int a,b,c;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
spfa();
printf("%d\n",dis[n]);
}
return 0;
}