标签：char 拓扑 for 距离 name space front mes bool
自己做出来固然开心，但是越发感觉到自己写题的确是很慢很慢了……往往有很多的细节反反复复的考虑才能确定，还要加油呀~
这道题目的突破口在于正难则反。直接求有多少不相交的不好求，我们转而求出所有相交的。我们先预处理出由 \(S\) 到 \(T\) 的最短路图（跑一边Dijkstra，所有的最短路径构成的图），显然可以顺便处理出 \(T\) 到 \(S\) 的。然后这个图是一个拓扑图，满足的性质就是从 \(S\) 点出发的任意一条路径终点均为 \(T\) 且为二者之间的最短路。拓扑图dp对于每个点我们又可以获得 \(Way1[u], Way2[u]\) 分别表示从起点到 \(u\) 点的总路径数和从终点到 \(u\) 的总路径数。
之后我们可以分类讨论一下，两条路径相遇是相遇在点上还是相遇在边上。相遇在点上很好判断，就是从起点到 \(u\) 点的距离正好等于从 \(u\) 点到终点的距离；相遇在边上则要求路径的终点落在这条边上，也是可以 O(1) 判断的。这样就好啦~(?´?`?)
#include using namespace std;
#define maxn 500000
#define mod 1000000007
#define int long long
int n, m, dis1[maxn], dis2[maxn];
int ans, K, S, T, Way1[maxn], Way2[maxn];
bool vis[maxn];
int read()
{
int x = 0, k = 1;
char c; c = getchar();
while(c ‘0‘ || c > ‘9‘) { if(c == ‘-‘) k = -1; c = getchar(); }
while(c >= ‘0‘ && c ‘9‘) x = x * 10 + c - ‘0‘, c = getchar();
return x * k;
}
struct edge
{
int cnp, fr[maxn], to[maxn], co[maxn];
int last[maxn], head[maxn], degree[maxn];
edge() { cnp = 2; }
void add(int u, int v, int w = 0)
{
fr[cnp] = u, to[cnp] = v, co[cnp] = w;
last[cnp] = head[u], head[u] = cnp ++;
}
}E[2], G;
struct node
{
int x, y;
node(int _x = 0, int _y = 0) { x = _x, y = _y; }
friend bool operator const node& a, const node& b)
{ return a.y > b.y; }
}; priority_queue q;
void Up(int &x, int y) { x = (x + y) % mod; }
int Qpow(int x) { return x * x % mod; }
void Dijk(int S, int *dis)
{
memset(vis, 0, sizeof(vis));
dis[S] = 0; q.push(node(S, 0));
while(!q.empty())
{
node now = q.top(); q.pop();
int u = now.x; if(vis[u]) continue; vis[u] = 1;
for(int i = G.head[u]; i; i = G.last[i])
{
int v = G.to[i];
if(dis[v] > dis[u] + G.co[i])
{
dis[v] = dis[u] + G.co[i];
q.push(node(v, dis[v]));
}
}
}
}
void Toposort()
{
memset(vis, 0, sizeof(vis));
queue int> q; q.push(S);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = G.head[u]; i; i = G.last[i])
{
int v = G.to[i];
if((dis1[u] + dis2[v] + G.co[i]) == K)
{
E[0].add(u, v); E[0].degree[v] ++;
E[1].add(v, u); E[1].degree[u] ++;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
void TopoDP(int opt, int *Way)
{
queue int> q;
for(int i = 1; i )
if(!E[opt].degree[i])
q.push(i), Way[i] = 1;
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = E[opt].head[u]; i; i = E[opt].last[i])
{
int v = E[opt].to[i];
E[opt].degree[v] --; Up(Way[v], Way[u]);
if(!E[opt].degree[v]) q.push(v);
}
}
}
signed main()
{
n = read(), m = read(); S = read(), T = read();
for(int i = 1; i )
{
int x = read(), y = read(), w = read();
G.add(x, y, w), G.add(y, x, w);
}
memset(dis1, 127, sizeof(dis1)); memset(dis2, 127, sizeof(dis2));
Dijk(S, dis1), Dijk(T, dis2);
K = dis1[T]; Toposort();
TopoDP(0, Way1); TopoDP(1, Way2);
for(int i = 1; i )
if(dis1[i] + dis1[i] == K)
Up(ans, Qpow(Way1[i] * Way2[i] % mod) % mod);
for(int i = 2; i 1].cnp; i ++)
{
int u = E[0].fr[i], v = E[0].to[i];
if(dis1[u] * 2 == K || dis1[v] * 2 == K) continue;
if(K > 2 * dis1[u] && K 2 * (K - dis2[v]))
Up(ans, Qpow(Way1[u] * Way2[v] % mod) % mod);
}
ans = (Way1[T] * Way1[T] % mod - ans + mod) % mod;
printf("%lld\n", ans);
return 0;
}
【题解】Atcoder ARC#90 E-Avoiding Collision
标签：char 拓扑 for 距离 name space front mes bool
原文地址：https://www.cnblogs.com/twilight-sx/p/9733849.html