1044 [HAOI2012]ROAD dijkstra递推求最短路径数+生成反向最短路拓扑图 计算以每个点为顶点，每条边上的最短路条数

本文主要是介绍1044 [HAOI2012]ROAD dijkstra递推求最短路径数+生成反向最短路拓扑图 计算以每个点为顶点，每条边上的最短路条数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 链接：https://ac.nowcoder.com/acm/contest/26077/1044
来源：牛客网

题目描述

C国有n座城市，城市之间通过m条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。

输入描述:

第一行包含两个正整数n、m
接下来m行每行包含三个正整数u、v、w，表示有一条从u到v长度为w的道路

输出描述:

输出应有m行，第i行包含一个数，代表经过第i条道路的最短路的数目对1000000007取模后的结果

示例1

输入

复制 4 4 1 2 5 2 3 5 3 4 5 1 4 8

4 4
1 2 5
2 3 5
3 4 5
1 4 8

输出

复制 2 3 2 1

2
3
2
1

备注:

30% 的数据满足：n≤15,m≤30n\leq 15, m\leq 30n≤15,m≤30。

60% 的数据满足：n≤300,m≤1000n\leq 300, m\leq 1000n≤300,m≤1000。

100% 的数据满足：n≤1500,m≤5000,w≤10000n\leq 1500, m\leq 5000, w\leq 10000n≤1500,m≤5000,w≤10000。

分析

https://blog.nowcoder.net/n/0ff8d480c1014a57821139788a23ed13?f=comment

题意：求在有向图上，以任意点为起点和终点，以每条边为相关边的最短路个数。

以任意点为起点和终点，

对于边<u,v> ，如果这条边是从 s 到 t 的最短路上的一条边，它作为相关边的最短路个数，根据乘法原理，就是s 到 t 的路径上，从s 到 u 的最短路个数 * v 到 t 的最短路个数。

从s 到 u 的最短路个数：

可以通过dijstra + dp 记录路径数来递推求得：（迪杰斯塔拉本质上也是一个拓扑序，当更新到后一个节点的时候，前面的节点不会再被更新，满足后无效性）

1.设起始点 的 路径数是1 cnt[s] = 1;

2.当dist[j] > dist[u] + w[i] 。此时 j 点的最短路个数 就是 u 点的最短路个数。 cnt[j] = cnt[u]

3.当dist[j] = dist[u] + w[i] 。此时 j 点的最短路个数 是 对 u 点的最短路个数的累加。 cnt[j] += cnt[u]

 

从 v 到 t 的最短路个数：

由于后无效性，没办法直接计算出 s 到 t 的 中间点 v 到 t 的最短路个数，但如果从 t 为起点建一个反向图，就可以知道了。

直接在dijkstra 跑最短路的时候 建一个拓扑图，只有最短路上的边才会被记录到这个图里，

1. 如果 dist[j]  > dist[u] + w[i] 。 先把之前更新过的边删掉：h1[j] = -1；然后再建一条反向边：add1（j ， u ）

2.如果 dist[j] == dist[u] + w[i]。说明这条边是最短路的边，直接建反向边：add1(j，u)

然后跑拓扑序，递推 cnt[j] += cnt[t] 就可以得到 到达 j 点的最短路个数。 cnt1[u] * cnt2[v] 就是 <u,v> 在这个 拓扑图里的贡献。

 

为什么要跑每个点？

因为起点不一样最短路也不一样，要计算的是 以每个点为起点每个点为终点的最短路。

 

//-------------------------代码----------------------------

#define int ll
const int N = 1e4+10,mod = 1e9+7;
int n,m;
int e[N],ne[N],w[N],h[N],idx,id[N];
void add(int a,int b,int c,int d) {e[idx] = b,ne[idx] = h[a],w[idx] = c,id[idx] = d,h[a] = idx ++ ;}
int e1[N],ne1[N],w1[N],h1[N],idx1,id1[N];
void add1(int a,int b,int d) {e1[idx1] = b,ne1[idx1] = h1[a],id1[idx1] = d,h1[a] = idx1 ++ ;}

bool vis[N];
int d[N],dist[N];
ll cnt1[N],cnt2[N],ans[N];

void init() {
    idx1 = 0;
    ms(h1,-1);
    ms(cnt1,0);
    ms(vis,0);
    ms(dist,0x3f);
}

void dijkstra(int s) {
    priority_queue<pii,V<pii>,greater<pii>>q;
    dist[s] = 0;q.push({0,s});cnt1[s] = 1;
    while(q.size()) {
        auto tmp = q.top();q.pop();int ver = tmp.y;
        if(vis[ver]) continue;vis[ver] = 1;
        for(int i = h[ver];~i;i = ne[i]) {
            int j = e[i];
            if(dist[j] == dist[ver] + w[i]) {
                add1(j,ver,id[i]);cnt1[j] = (cnt1[j] + cnt1[ver]) % mod;
            } else if(dist[j] > dist[ver] + w[i] ) {
                h1[j] = -1;add1(j,ver,id[i]);dist[j] = dist[ver] + w[i];
                cnt1[j] = cnt1[ver];q.push({dist[j],j});
            }
        }
    }
}

void topsort() {
    queue<int> q;
    fo(i,1,n) {
        for(int j = h1[i];~j;j=ne1[j]) {
            int son = e1[j];
            d[son] ++;
        }
    }
    fo(i,1,n) {
        if(!d[i]) q.push(i);
        cnt2[i] = 1;
    }
    while(q.size()) {
        auto t = q.front();q.pop();
        for(int i = h1[t];~i;i=ne1[i]) {
            int j = e1[i];
            cnt2[j] = (cnt2[j] + cnt2[t]) % mod;
            ans[id1[i]] = (ans[id1[i]] + cnt1[j] * cnt2[t] % mod) % mod;
            if(-- d[j] == 0) q.push(j);
        }
    }
}

void solve()
{
    cin>>n>>m;
    ms(h,-1);
    fo(i,1,m) {
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w,i);
    }
    fo(i,1,n) {
        init();
        dijkstra(i);
        topsort();
    }
    fo(i,1,m) cout<<ans[i]<<endl;
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

这篇关于1044 [HAOI2012]ROAD dijkstra递推求最短路径数+生成反向最短路拓扑图 计算以每个点为顶点，每条边上的最短路条数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！