Liveddd's Blog

愛にできることはまだあるかい

P2505 [HAOI2012]道路

发表于 更新于 分类于
本文字数： 3.2k 阅读时长 ≈ 7 分钟

最短路 DAG。

首先，我们很容易知道：$i\to j$ 的最短路径的任意子路径 $u\to v$ 都是最短路径，接着我们可以得到另一个结论：若存在一条子路径 $u\to v$ 不是最短路径，那么很明显可以找到一条更短的 $u\to v$ 使得 $i\to j$ 更短。根据这个原则，我们可以得出在固定源点下，存在 $G$ 的一个子图 $G’$，使得 $G’$ 的每一条边都在 $S$ 到其他至少一个点的最短路径上，且 $G’$ 以外的边不在 $S$ 到任意一个点的最短路径上。这里把称 $G’$ 为源点为 $S$ 时 $G$ 的最短路图。而求出最短路图的方式很简单，就是如果有 $dis_{v_i}=dis_{u_i}+w_i$，我们给这条路打上一个标记就行了。

容易得到这个最短路图是无环的，我们就可以在最短路图上进行拓扑排序。考虑维护两个数组为 $cnt1_i$ 与 $cnt2_i$ 。接着我们考虑正反两次拓扑分别表示 $i\to u$ 和 $v\to j$ 的最短路径条数，而答案就为 $cnt_1({u_i})*cnt_2({v_i})$ 之和。

使用 Dijkstra 的话时间复杂度应该是 $\mathcal O(nm\log n + n^2)$，只不过这里用了 SPFA。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1500+10,M=5000+10;
const int mod=1e9+7;
int n,m;
int tot,head[N],ver[M],e[M],ne[M];
int u[M],v[M],w[M];
int dis[N],vis[N];
int flag[M],ans[M];
int len,top[N],deg[N];
int cnt1[N],cnt2[N];
void add(int u,int v,int w)
{
    ver[++tot]=v;
    e[tot]=w;
    ne[tot]=head[u];
    head[u]=tot;
}
void SPFA(int s)
{
    queue<int>q;
    q.push(s);
    dis[s]=0;
    vis[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=head[now];i;i=ne[i])
        {
            int to=ver[i];
            if(dis[to]>dis[now]+e[i])
            {
                dis[to]=dis[now]+e[i];
                if(!vis[to])
                {
                    vis[to]=1;
                    q.push(to);
                }
            }
        }
    }
    for(int i=1;i<=m;i++)
        if(dis[v[i]]==dis[u[i]]+w[i])
            flag[i]=1;
}
void init()
{
    memset(dis,0x3f,sizeof(dis));
    memset(flag,0,sizeof(flag));
    memset(cnt1,0,sizeof(cnt1));
    memset(cnt2,0,sizeof(cnt2));
}
void topo(int s)
{
    queue<int>q;
    for(int i=1;i<=m;i++)
        if(flag[i])deg[v[i]]++;
    cnt1[s]++;
    q.push(s);
    len=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        top[++len]=now;
        for(int i=head[now];i;i=ne[i])
        {
            if(!flag[i])continue;
            int to=v[i];
            if(!--deg[v[i]])q.push(to);
            cnt1[to]=(cnt1[to]+cnt1[now])%mod;
        }
    }
    for(int i=len;i>=1;i--)
    {
        int now=top[i];
        cnt2[now]++;
        for(int j=head[now];j;j=ne[j])
        {
            if(!flag[j])continue;
            int to=ver[j];
            cnt2[now]=(cnt2[now]+cnt2[to])%mod;
        }
    }
}
void solve(int s)
{
    init();
    SPFA(s);
    topo(s);
    for(int i=1;i<=m;i++)
        if(flag[i])
            ans[i]=(ans[i]+cnt1[u[i]]*cnt2[v[i]])%mod;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i]>>w[i];
        add(u[i],v[i],w[i]);
    }
    for(int i=1;i<=n;i++)
        solve(i);
    for(int i=1;i<=m;i++)
        cout<<ans[i]<<"\n";
    return 0;
}