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

Re:spfa 1A 水之!!附代码!!

Posted by osprey at 2014-05-21 18:36:04 on Problem 3268
In Reply To:spfa 1A 水之!!附代码!! Posted by:wocha at 2012-08-21 09:51:49
> #include <queue>
> #include <cstdio>
> #include <iostream>
> #define M 101000
> #define inf 0x3f3f3f3f
> using namespace std;
> int start[M],e,end[M],next[M],cost[M];
> inline void Init(){
> 	e=0;  memset(start,-1,sizeof(start));
> }
> inline void add(int u2,int v2,int w2){
> 	end[e]=v2;
> 	cost[e]=w2;
> 	next[e]=start[u2];
> 	start[u2]=e++;
> }
> int vis[M],cnt[M],d[M];
> void spfa (int st,int N){
> 	
> 	memset(vis,0,N+2);
> 	memset(cnt,0,N+2);
> 	memset(d,inf,sizeof(d));
> 	queue<int > Q; int u1,v1, w1;
> 	Q.push(st), vis[st]=1, cnt[st]++, d[st]=0;
> 	while(!Q.empty()){
> 		u1=Q.front();Q.pop();vis[u1]=0;
> 		for(int i=start[u1];i!=-1;i=next[i]){
> 			v1=end[i];  w1=cost[i];
> 			if(d[v1]>d[u1]+w1){
> 				d[v1]=d[u1]+w1;
> 				if(!vis[v1]){
> 					vis[v1]=1;
> 					Q.push(v1);
> 					if(++cnt[v1]>N) return;
> 				}
> 			}
> 		}
> 	}
> }
> int u[M],v[M],w[M],d1[M];
> int main(){
> 	int n,m,x;
> 	while(~scanf("%d%d%d",&n,&m,&x)){
>      Init();
> 	 for(int i=0;i<m;i++){
>  		scanf("%d%d%d",u+i,v+i,w+i);
>  		add(u[i],v[i],w[i]);
>  	}	
>  	 spfa(x,n);
>  	 for(int i=1;i<=n;i++)  d1[i]=d[i];
>  	 Init();
>  	 for(int i=0;i<m;i++)	add(v[i],u[i],w[i]);
>  	 spfa(x,n);
>  	 int max1=-inf;
>  	 for(int i=1;i<=n;i++)
>  	  if(i!=x) max1=max1<(d1[i]+d[i])?(d1[i]+d[i]):max1;
>  	 printf("%d\n",max1);
> 	}
> }

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