Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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++)
			scanf("%d%d%d",&x,&y,&w),addedge(x,y,w);
		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])
				if(map[i]!=map[to[j]])	caddedge(map[i],map[to[j]],val[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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator