Description

题库链接

给出一张 \(N\) 个节点， \(M\) 条边的无向图，给出起点 \(S\) 和终点 \(T\) 。询问两个人分别从 \(S\) 和 \(T\) 出发，走最短路不相遇的方案数。

\(1 \leq N \leq 100,000,1 \leq M \leq 200,000\)

Solution

记最短路长度为 \(D\) ，从 \(S\) 出发走过的路程为 \(d_1\) ，从 \(T\) 出发的走过的路程为 \(d_2\) 。值得注意的是走最短路相遇只会出现两种情况：

1. 在某个节点相遇，此时 \(d_1=d_2=\frac{D}{2}\) ；
2. 在某条边上相遇，记这条边为 \(e\) ，边权为 \(c\) ，连接 \(u,v\) 两个节点。此时 \({d_1}_u+{d_2}_v+c=D\) ，且 \({d_1}_u < \left\lfloor\frac{D}{2}\right\rfloor,{d_2}_v < \left\lfloor\frac{D}{2}\right\rfloor\)

那么我们跑一遍最短路计数，用总方案数减去上述不合法的情况即可。

Code

//It is made by Awson on 2018.2.2

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

#define writeln(x) (write(x), putchar('\n'))

#define lowbit(x) ((x)&(-(x)))

using namespace std;

const int N = 100000;

const int yzd = 1e9+7;

void read(int &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(int x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(int x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n, m, s, t, u, v, c;

struct tt {int to, next, cost; }edge[(N<<2)+5];

int path[N+5], top;

int ans1[N+5], ans2[N+5], vis[N+5], in[N+5];

LL dist1[N+5], dist2[N+5];

queue<int>Q;

vector<int>to[N+5];

void add(int u, int v, int c) {

    edge[++top].to = v, edge[top].cost = c, edge[top].next = path[u], path[u] = top;

}

void SPFA(int s, LL *dist) {

    dist[s] = 0; Q.push(s); vis[s] = 1;

    while (!Q.empty()) {

    int u = Q.front(); Q.pop(); vis[u] = 0;

    for (int i = path[u]; i; i = edge[i].next)

        if (dist[edge[i].to] > dist[u]+edge[i].cost) {

        dist[edge[i].to] = dist[u]+edge[i].cost;

        if (!vis[edge[i].to]) {

            vis[edge[i].to] = 1; Q.push(edge[i].to);

        }

        }

    }

}

void topsort(int s, LL *dist, int *ans) {

    for (int u = 1; u <= n; u++) {

    to[u].clear();

    for (int i = path[u]; i; i = edge[i].next)

        if (dist[edge[i].to] == dist[u]+edge[i].cost) to[u].push_back(edge[i].to), ++in[edge[i].to];

    }

    ans[s] = 1; Q.push(s);

    while (!Q.empty()) {

    int u = Q.front(), size = to[u].size(); Q.pop();

    for (int i = 0; i < size; i++) {

        if (--in[to[u][i]] == 0) Q.push(to[u][i]); (ans[to[u][i]] += ans[u]) %= yzd;

    }

    }

}

void work() {

    read(n), read(m), read(s), read(t);

    for (int i = 1; i <= m; i++) {

    read(u), read(v), read(c); add(u, v, c); add(v, u, c);

    }

    memset(dist1, 127/3, sizeof(dist1));

    SPFA(s, dist1); topsort(s, dist1, ans1);

    memset(dist2, 127/3, sizeof(dist2));

    SPFA(t, dist2); topsort(t, dist2, ans2);

    int ans = 1ll*ans1[t]*ans1[t]%yzd;

    for (int u = 1; u <= n; u++) {

    if (dist1[u] == dist2[u] && dist2[u]*2 == dist1[t]) (ans -= 1ll*ans1[u]*ans1[u]%yzd*ans2[u]%yzd*ans2[u]%yzd) %= yzd;

    for (int i = path[u]; i; i = edge[i].next)

        if (dist1[u]+edge[i].cost+dist2[edge[i].to] == dist1[t] && dist1[u]*2 < dist1[t] && dist2[edge[i].to]*2 < dist1[t])

        (ans -= 1ll*ans1[u]*ans1[u]%yzd*ans2[edge[i].to]%yzd*ans2[edge[i].to]%yzd) %= yzd;

    }

    writeln((ans+yzd)%yzd);

}

int main() {

    work();

    return 0;

}