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

## WA了N次，从N搜到1就WA，一改成从1搜到N就过了，，，附上AC代码

Posted by fenglin2013 at 2014-04-27 13:38:07 on Problem 2387
```#include<stdio.h>
#include<string.h>
#define S scanf
#define P printf
#define INF 999999
int map[1001][1001],q[400000],dis[10001],visit[10001];
int n;
void spfa(int s,int m)
{
int i,k,str=0,end=1;
q[str] = s;
dis[s] = 0;
while(str<end)
{
k = q[str];
visit[k]=0;
/*for(i=str;i<end;i++)
P("%d ",q[i]);
P("\n");*/
for(i=1;i<=m;i++)
{
if(map[k][i]>0 && dis[i] > map[k][i] + dis[k])
{
dis[i] = dis[k] + map[k][i];
if(!visit[i])
{
q[end++] = i;
visit[i] = 1;
}
}
}
str++;
}
}
int main()
{
int i,j,t,tmp1,tmp2,ans,tmp3;
while(~S("%d%d",&t,&n))
{
memset(map,-1,sizeof(map));
memset(visit,0,sizeof(visit));
memset(dis,INF,sizeof(dis));
for(i=0;i<t;i++)
{
S("%d%d",&tmp1,&tmp2);
//tmp3=tmp1>tmp2?tmp1:tmp2;
//tmp2=tmp1<tmp2?tmp1:tmp2;
//tmp1=tmp3;
S("%d",&tmp3);
if(map[tmp2][tmp1]!=-1)
{
map[tmp2][tmp1]=tmp3<map[tmp1][tmp2]?tmp3:map[tmp1][tmp2];
map[tmp1][tmp2]=map[tmp2][tmp1];
}
else
{
map[tmp1][tmp2]=tmp3;
map[tmp2][tmp1]=tmp3;
}
}
dis[1]=0;
spfa(1,n);
/*
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
P("%d ",map[i][j]);
}
P("\n");
}
for(i=1;i<=n;i++)
P("%d ",dis[i]);
P("\n");*/
P("%d\n",dis[n]);
}
}
/*
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
*/
```

Followed by: