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 yousiki at 2016-04-20 21:36:40 on Problem 3114
```RT 我用的是Tarjan缩点+SPFA跑最短路
WA了，看不出来错误，求大神指点

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=500,maxm=250005,MAX=1000000;
int n,m,c,hd[maxn],nt[maxm],to[maxm],val[maxm],cnt;
int hd2[maxn],to2[maxm],nt2[maxm],val2[maxm],cnt2,dis[maxn][maxn];
int dfn[maxn],low[maxn],st[maxn],sin[maxn],map[maxn],p,mp,tot;
inline void addedge(int x,int y,int w){
nt[cnt]=hd[x];
to[cnt]=y;
val[cnt]=w;
hd[x]=cnt++;
}
inline void caddedge(int x,int y,int w){
nt2[cnt2]=hd2[x];
to2[cnt2]=y;
val2[cnt2]=w;
hd2[x]=cnt2++;
}
inline void Tarjan(int u){
dfn[u]=low[u]=++tot;
st[p++]=u,sin[u]=1;
for(int i=hd[u];~i;i=nt[i]){
if(!dfn[to[i]]){
Tarjan(to[i]);
low[u]=min(low[u],low[to[i]]);
}
else if(sin[to[i]])
low[u]=min(low[u],dfn[to[i]]);
}
if(low[u]==dfn[u]){
int t;
++mp;
do{
t=st[--p];
sin[t]=0;
map[t]=mp;
}
while(t!=u);
}
}
inline void SPFA(int u){
for(int i=1;i<=mp;i++)
dis[u][i]=MAX;
dis[u][u]=0;
queue<int> q;
int vis[maxn];
memset(vis,0,sizeof(vis));
vis[u]=1;
q.push(u);
while(!q.empty()){
int t=q.front();
q.pop();
vis[t]=0;
for(int i=hd2[t];~i;i=nt2[i])
if(dis[u][to2[i]]>dis[u][t]+val2[i]){
dis[u][to2[i]]=dis[u][t]+val2[i];
if(!vis[to2[i]])q.push(to2[i]),vis[to2[i]]=1;
}
}
}
int main(){
while(scanf("%d%d",&n,&m)&&n){
memset(hd,-1,sizeof(hd));
memset(hd2,-1,sizeof(hd2));
memset(dfn,0,sizeof(dfn));
for(int i=0;i<maxn;i++)	dis[i][0]=0;
mp=cnt=cnt2=tot=p=0;
for(int i=0,x,y,w;i<m;i++)
for(int i=1;i<=n;i++)
if(!dfn[i])	Tarjan(i);
for(int i=1;i<=n;i++)
for(int j=hd[i];~j;j=nt[j])
scanf("%d",&c);
for(int k=0,x,y;k<c;k++){
scanf("%d%d",&x,&y);
x=map[x],y=map[y];
if(!dis[x][0])	SPFA(x),dis[x][0]=1;
if(dis[x][y]>=MAX)	printf("Nao e possivel entregar a carta\n");
else printf("%d\n",dis[x][y]);
}
printf("\n");
}
return 0;
}
```

Followed by: