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

## 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;
> 		dista[MAXN],distb[MAXN],cnta[MAXN],cntb[MAXN];
>
> inline void addedge(int u,int v,int w)
> {
> 		tot++;
> }
> inline void addredge(int u,int v,int w)
> {
> 		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++)
> 				{
> 						cnta[i] = cntb[i] = -1;
> 				}
> 				for (i = 1; i <= m; i++)
> 				{
> 						scanf("%d%d%d",&u[i],&v[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: