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

## spfa 32ms~

Posted by evenbao at 2018-08-06 12:41:34 on Problem 3463
```#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:

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