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

## 求个测试数据，为什么是错得？？

Posted by hkj_fh at 2014-06-08 21:08:15 on Problem 3255
```#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#define N 5010
#define inf 1<<31-1
using namespace std;
int dis[2][N];
struct node{
int to;
int dis;
};
vector<node>mp[N];
queue<int>q;
bool in_q[N];
int spfa(int st,int ed)
{
int i,ui,si,mdis;
for(i=0;i<=ed+9;i++)
{
in_q[i]=false;
dis[0][i]=dis[1][i]=inf;
}
while(!q.empty())
q.pop();
q.push(st);
in_q[st]=true;
dis[0][st]=0;
while(!q.empty())
{
si=q.front();
q.pop();
in_q[si]=false;
for(i=0;i<mp[si].size();i++)
{
ui=mp[si][i].to;
mdis=mp[si][i].dis+dis[0][si];
if(mdis<dis[0][ui])
{
dis[1][ui]=dis[0][ui];
dis[0][ui]=mdis;
if(!in_q[ui]){
q.push(ui);
in_q[ui]=true;
}
}
else{
if(mdis<dis[1][ui]&&mdis!=dis[0][ui])
dis[1][ui]=mdis;
}
if(dis[1][si]+mp[si][i].dis<dis[1][ui])
dis[1][ui]=dis[1][si]+mp[si][i].dis;
}
}
return dis[1][ed];
}
int main()
{
int n,m,ans;
int i,a,b,d;
node temp;
while(~scanf("%d%d",&n,&m))
{
for(i=0;i<=n;i++)
mp[i].clear();
for(i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&d);
temp.dis=d;
temp.to=b;
mp[a].push_back(temp);
temp.to=a;
mp[b].push_back(temp);
}
ans=spfa(1,n);
//        for(i=1;i<=n;i++)
//            printf("%d %d\n",dis[0][i],dis[1][i]);
printf("%d\n",ans);
}
return 0;
}
```

Followed by: