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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:spfa 32ms~

Posted by Fangs at 2019-06-12 19:19:57 on Problem 3463
In Reply To:spfa 32ms~ Posted by:evenbao at 2018-08-06 12:41:34
> #include <algorithm>  
> #include <bitset>  
> #include <cctype>  
> #include <cerrno>  
> #include <clocale>  
> #include <cmath>  
> #include <complex>  
> #include <cstdio>  
> #include <cstdlib>  
> #include <cstring>  
> #include <ctime>  
> #include <deque>  
> #include <exception>  
> #include <fstream>  
> #include <functional>  
> #include <limits>  
> #include <list>  
> #include <map>  
> #include <iomanip>  
> #include <ios>  
> #include <iosfwd>  
> #include <iostream>  
> #include <istream>  
> #include <ostream>  
> #include <queue>  
> #include <set>  
> #include <sstream>  
> #include <stdexcept>  
> #include <streambuf>  
> #include <string>  
> #include <utility>  
> #include <vector>  
> #include <cwchar>  
> #include <cwctype>  
> #include <stack>  
> #include <limits.h>
> using namespace std;
> #define MAXN 2010
> #define MAXM 20010
> const int INF = 2e9;
> 
> struct edge
> {
> 		int to,w,nxt;
> } e[MAXM << 1];
> 
> int i,n,m,ans,tot,tmp,val,shortest,S,T,TC;
> int head[MAXN],rhead[MAXN],u[MAXM],v[MAXM],w[MAXM],
> 		dista[MAXN],distb[MAXN],cnta[MAXN],cntb[MAXN];
> 
> inline void addedge(int u,int v,int w)
> {
> 		tot++;
> 		e[tot] = (edge){v,w,head[u]};
> 		head[u] = tot;
> }
> inline void addredge(int u,int v,int w)
> {
> 		tot++;
> 		e[tot] = (edge){v,w,rhead[u]};
> 		rhead[u] = tot;
> }
> inline void spfa1(int s)
> {
> 		int i,l,r,u,v,w;
> 		static int q[MAXN];
> 		static bool inq[MAXN];
> 		for (i = 1; i <= n; i++) 
> 		{
> 				dista[i] = INF;
> 				inq[i] = false;
> 		}
> 		q[l = r = 1] = s;
> 		inq[s] = true;
> 		dista[s] = 0; 
> 		while (l <= r)
> 		{
> 				u = q[l];
> 				l++;
> 				inq[u] = false;
> 				for (i = head[u]; i; i = e[i].nxt)
> 				{
> 						v = e[i].to;
> 						w = e[i].w;
> 						if (dista[u] + w < dista[v])
> 						{
> 								dista[v] = dista[u] + w;
> 								if (!inq[v])
> 								{
> 										inq[v] = true;
> 										q[++r] = v;
> 								}
> 						} 
> 				}
> 		}
> }
> inline void spfa2(int s)
> {
> 		int i,l,r,u,v,w;
> 		static int q[MAXN];
> 		static bool inq[MAXN];
> 		for (i = 1; i <= n; i++)
> 		{
> 				distb[i] = INF;
> 				inq[i] = false;
> 		}
> 		q[l = r = 1] = s;
> 		distb[s] = 0; 
> 		inq[s] = true;
> 		while (l <= r)
> 		{
> 				u = q[l];
> 				l++;
> 				inq[u] = false;
> 				for (i = rhead[u]; i; i = e[i].nxt)
> 				{
> 						v = e[i].to;
> 						w = e[i].w;
> 						if (distb[u] + w < distb[v])
> 						{
> 								distb[v] = distb[u] + w;
> 								if (!inq[v])
> 								{
> 										inq[v] = true;
> 										q[++r] = v;
> 								}
> 						} 
> 				}
> 		}
> }
> inline int dp1(int u)
> {
> 		int i,v,w;
> 		if (cnta[u] != -1) return cnta[u];
> 		if (u == S) return cnta[u] = 1;
> 		cnta[u] = 0;
> 		for (i = rhead[u]; i; i = e[i].nxt)
> 		{
> 				v = e[i].to;
> 				w = e[i].w;
> 				if (dista[v] + w == dista[u]) cnta[u] += dp1(v);
> 		}
> 		return cnta[u];
> }
> inline int dp2(int u)
> {
> 		int i,v,w;
> 		if (cntb[u] != -1) return cntb[u];
> 		if (u == T) return cntb[u] = 1;
> 		cntb[u] = 0;
> 		for (i = head[u]; i; i = e[i].nxt)
> 		{
> 				v = e[i].to;
> 				w = e[i].w;
> 				if (dista[u] + w == dista[v]) cntb[u] += dp2(v);
> 		}
> 		return cntb[u];
> }
> int main() 
> {
> 		
> 		scanf("%d",&TC);
> 		while (TC--)
> 		{
> 				scanf("%d%d",&n,&m);
> 				tot = 0;
> 				for (i = 1; i <= n; i++) 
> 				{
> 						head[i] = rhead[i] = 0;
> 						cnta[i] = cntb[i] = -1;
> 				}
> 				for (i = 1; i <= m; i++)
> 				{
> 						scanf("%d%d%d",&u[i],&v[i],&w[i]);
> 						addedge(u[i],v[i],w[i]);
> 						addredge(v[i],u[i],w[i]);
> 				}		
> 				scanf("%d%d",&S,&T);
> 				spfa1(S);
> 				spfa2(T);
> 				for (i = 1; i <= n; i++) dp1(i);
> 				for (i = 1; i <= n; i++) dp2(i);
> 				shortest = dista[T];
> 				ans = cnta[T];
> 				for (i = 1; i <= m; i++)
> 				{
> 						tmp = dista[u[i]] + w[i] + distb[v[i]];
> 						if (dista[u[i]] + w[i] == dista[v[i]] + 1 && tmp == shortest + 1) ans += cnta[u[i]] * cntb[v[i]];
> 				}
> 				printf("%d\n",ans);
> 		}
> 		
> 		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