Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 救命，spfa

Posted by cghAndy at 2013-10-26 21:52:43 on Problem 2387
```#include<cstdio>
#include<cstring>
using namespace std;
struct edge
{
int x,y,d,next;
}a[21000];int len,first[2100];
void ins(int x,int y,int dd)
{
len++;
a[len].x=x; a[len].y=y;a[len].d=dd;
a[len].next=first[x];first[x]=len;
}
bool v[2100];int d[2100],n,st,ed,m;
int main()
{
int x,y,k,i,j;
while(scanf("%d%d",&n,&m)!=EOF){
st=1;ed=m;
memset(first,0,sizeof(first)); len=0;
for(i=1;i<=n;i++){scanf("%d%d%d",&x,&y,&k);ins(x,y,k);}
memset(d,63,sizeof(d));d[st]=0;
memset(v,false,sizeof(v));
list[1]=st;v[st]=true;
for(k=first[x];k;k=a[k].next){
y=a[k].y;
if(d[y]>d[x]+a[k].d){
d[y]=d[x]+a[k].d;
if(v[y]==false){
v[y]=true;
list[tail]=y;
tail++; if(tail==n+1)tail=1;
}
}
}
v[x]=false;
}
printf("%d\n",d[ed]);
}
return 0;
}```

Followed by: