2010-1112

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：
给定一有向图，查询从0开始到达每一个点的最短路中经过某点x的最短路数有多少。

解法：
因为查询的是最短路，所以从0开始做最短路，即可得到一有向无环图。
题目中查询某一点x的答案相当于以该点为终点的最短路数(end[x])与以该点为起点的最短路数(begin[x])的乘积
ans[x] = end[x] * begin[x]
其中end[x]可以在求最短路的时候顺带求出。
begin[x]由于是有向无环图，所有按拓扑关系dp一下即可
begin[x] = sigma{begin[k] : dist[0][k] = dist[0][x] + edge[x][k]} + 1
其中dist[0][x]为从0到x最短路的长度
注意最后输出的是10位数，所以乘法会爆long long，需要特别处理一下

代码：
{{{
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

typedef long long LL;

const int MAXN = 11000;
const int INF = 1000000000;
const LL MOD = 10000000000LL;

priority_queue<pair<int, int> > Q;
vector<pair<int, int> > v[MAXN], rv[MAXN];
vector<int> list;

int N, dis[MAXN];
LL begin[MAXN], end[MAXN], ans[MAXN];

void solve() {

    for (int i = 0; i < N; i++) dis[i] = INF, end[i] = 0;
    dis[0] = 0;
    end[0] = 1;
    Q.push(make_pair(0, 0));
    list.clear();
    while (!Q.empty()) {
        int cur = Q.top().second, len = -Q.top().first;
        Q.pop();
        if (dis[cur] != len) continue;
        list.push_back(cur);
        end[cur] %= MOD;
        for (int i = 0; i < (int)v[cur].size(); i++) {
            int next = v[cur][i].first, d = dis[cur] + v[cur][i].second;
            if (dis[next] > d) {
                dis[next] = d;
                end[next] = end[cur];
                Q.push(make_pair(-dis[next], next));
            }
            else if (dis[next] == d){
                end[next] += end[cur];
            }
        }   
    }
    for (int i = 0; i < N; i++) begin[i] = 1;
    for (int i = (int)list.size() - 1; i >= 0; i--) {
        int cur = list[i];
        begin[cur] %= MOD;
        for (int j = 0; j < (int)rv[cur].size(); j++) {
            if (rv[cur][j].second + dis[rv[cur][j].first] != dis[cur]) continue;
            begin[rv[cur][j].first] += begin[cur];
        }
    }

    int a[100], b[100], c[100];
    for (int t = 0; t < N; t++) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        LL now = 1;
        for (int j = 0; j < 10; j++) {
            a[j] = begin[t] / now % 10;
            now *= 10;          
        }
        now = 1;
        for (int j = 0; j < 10; j++) {
            b[j] = end[t] / now % 10;
            now *= 10;
        }       
        memset(c, 0, sizeof(c));
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++) 
                c[i + j] += a[i] * b[j];
        for (int i = 0; i < 10; i++) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        ans[t] = 0;
        now = 1;
        for (int i = 0; i < 10; i++) { 
            ans[t] += c[i] * now;
            now *= 10;
        }
    }   
}

void print(int cur) {
    LL now = 1000000000LL;
    for (int i = 0; i < 10; i++) {
        printf("%lld", ans[cur] / now % 10);
        now /= 10;
    }
    puts("");
}

int main() {

    int M, Q, a, b, c;
    while (scanf("%d %d %d", &N, &M, &Q) != EOF) {
        for (int i = 0; i < N; i++) {
            v[i].clear();
            rv[i].clear();
        }
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &a, &b, &c);
            v[a].push_back(make_pair(b, c));
            rv[b].push_back(make_pair(a, c));
        }   
        solve();
        for (int i = 0; i < Q; i++) {
            scanf("%d", &a);
            print(a);
        }
    }
    return 0;
}
}}}

题意：

给定一有向图，查询从0开始到达每一个点的最短路中经过某点x的最短路数有多少。

解法：

因为查询的是最短路，所以从0开始做最短路，即可得到一有向无环图。

题目中查询某一点x的答案相当于以该点为终点的最短路数(end[x])与以该点为起点的最短路数(begin[x])的乘积

ans[x] = end[x] * begin[x]

其中end[x]可以在求最短路的时候顺带求出。

begin[x]由于是有向无环图，所有按拓扑关系dp一下即可

begin[x] = sigma{begin[k] : dist[0][k] = dist[0][x] + edge[x][k]} + 1

其中dist[0][x]为从0到x最短路的长度

注意最后输出的是10位数，所以乘法会爆long long，需要特别处理一下

代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
const int MAXN = 11000;
const int INF = 1000000000;
const LL MOD = 10000000000LL;
priority_queue<pair<int, int> > Q;
vector<pair<int, int> > v[MAXN], rv[MAXN];
vector<int> list;
int N, dis[MAXN];
LL begin[MAXN], end[MAXN], ans[MAXN];
void solve() {
    for (int i = 0; i < N; i++) dis[i] = INF, end[i] = 0;
    dis[0] = 0;
    end[0] = 1;
    Q.push(make_pair(0, 0));
    list.clear();
    while (!Q.empty()) {
        int cur = Q.top().second, len = -Q.top().first;
        Q.pop();
        if (dis[cur] != len) continue;
        list.push_back(cur);
        end[cur] %= MOD;
        for (int i = 0; i < (int)v[cur].size(); i++) {
            int next = v[cur][i].first, d = dis[cur] + v[cur][i].second;
            if (dis[next] > d) {
                dis[next] = d;
                end[next] = end[cur];
                Q.push(make_pair(-dis[next], next));
            }
            else if (dis[next] == d){
                end[next] += end[cur];
            }
        }   
    }
    for (int i = 0; i < N; i++) begin[i] = 1;
    for (int i = (int)list.size() - 1; i >= 0; i--) {
        int cur = list[i];
        begin[cur] %= MOD;
        for (int j = 0; j < (int)rv[cur].size(); j++) {
            if (rv[cur][j].second + dis[rv[cur][j].first] != dis[cur]) continue;
            begin[rv[cur][j].first] += begin[cur];
        }
    }
    int a[100], b[100], c[100];
    for (int t = 0; t < N; t++) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        LL now = 1;
        for (int j = 0; j < 10; j++) {
            a[j] = begin[t] / now % 10;
            now *= 10;          
        }
        now = 1;
        for (int j = 0; j < 10; j++) {
            b[j] = end[t] / now % 10;
            now *= 10;
        }       
        memset(c, 0, sizeof(c));
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < 10; j++) 
                c[i + j] += a[i] * b[j];
        for (int i = 0; i < 10; i++) {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
        ans[t] = 0;
        now = 1;
        for (int i = 0; i < 10; i++) { 
            ans[t] += c[i] * now;
            now *= 10;
        }
    }   
}
void print(int cur) {
    LL now = 1000000000LL;
    for (int i = 0; i < 10; i++) {
        printf("%lld", ans[cur] / now % 10);
        now /= 10;
    }
    puts("");
}
int main() {
    int M, Q, a, b, c;
    while (scanf("%d %d %d", &N, &M, &Q) != EOF) {
        for (int i = 0; i < N; i++) {
            v[i].clear();
            rv[i].clear();
        }
        for (int i = 0; i < M; i++) {
            scanf("%d %d %d", &a, &b, &c);
            v[a].push_back(make_pair(b, c));
            rv[b].push_back(make_pair(a, c));
        }   
        solve();
        for (int i = 0; i < Q; i++) {
            scanf("%d", &a);
            print(a);
        }
    }
    return 0;
}