题解 SP3545 【NAJKRACI - Najkraci】

Solution Najkraci

最短路，动态规划，计数

---

分析:

由于\(n\)范围较小，我们可以枚举最短路的源点，然后显然在最短路边上的边构成了一个\(DAG\)，我们在\(DAG\)上做\(dp\)就好

我们记\(to[u]\)表示在\(DAG\)上源点有多少条路径到达\(u\)，\(from[u]\)表示在\(DAG\)上从\(u\)出发有多少条路径到达其它点

记源点为\(s\),\(to[s]=1\)，假设有向边为\((u,v)\)，那么\(to[v] = \sum to[u]\)

同理\(from[u]=\sum from[v]+1\)(因为\(u\)点到自己的路径也要纳入其中)

然后一条边\((u,v)\)以\(s\)为源点时被最短路包括的次数就是\(to[u] \times from[v]\)

\(to\)可以在跑\(Dijkstra\)的时候计算，有个\(Trick\)就是每次\(u\)松弛\(v\)的时候把\(to[v]\)重置为\(0\)，因为\(u\)松弛\(v\)后前面松弛过\(v\)的边不可能成为\(DAG\)的一部分

\(from\)以跑\(Dijkstra\)顺序的逆序计算即可

枚举源点跑\(n\)次\(Dijkstra\)即可得出答案

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 2e3,maxm = 2e4,mod = 1e9 + 7;
inline int read(){
    int x = 0;char c = getchar();
    while(!isdigit(c))c = getchar();
    while(isdigit(c))x = x * 10 + c - '0',c = getchar();
    return x;
}
struct Edge{
    int from,to,dis;
}Edges[maxm];
int head[maxn],nxt[maxm],tot = 1,n,m;
inline void addedge(int from,int to,int dis){
    Edges[++tot] = Edge{from,to,dis};
    nxt[tot] = head[from];
    head[from] = tot;
}
ll ans[maxm],from[maxn],to[maxn];
int dis[maxn],vis[maxn];
vector<int> topo;
struct HeapNode{
    int u,h;
    bool operator < (const HeapNode &rhs)const{
        return h > rhs.h;
    }
};
priority_queue<HeapNode> Q;
inline void dijkstra(int s){
    memset(from,0,sizeof(from));
    memset(to,0,sizeof(to));
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[s] = 0,to[s] = 1;topo.clear();
    Q.push(HeapNode{s,dis[s]});
    while(!Q.empty()){
        int u = Q.top().u;Q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        topo.push_back(u);
        for(int i = head[u];i;i = nxt[i])
            if(!(i & 1)){
                const Edge &e = Edges[i];
                if(dis[e.from] + e.dis > dis[e.to])continue;//有重边
                if(dis[e.from] + e.dis < dis[e.to]){
                    to[e.to] = 0;
                    dis[e.to] = dis[e.from] + e.dis;
                    Q.push(HeapNode{e.to,dis[e.to]});
                }
                to[e.to] = (to[e.to] + to[u]) % mod;
            }
    }
    for(auto it = topo.rbegin();it != topo.rend();it++){
        from[*it]++;
        for(int i = head[*it];i;i = nxt[i])
            if(i & 1){
                const Edge &e = Edges[i];
                if(dis[e.to] + e.dis == dis[e.from])
                    from[e.to] += from[*it],from[e.to] %= mod;
            }
    }
    for(int i = 2;i <= tot;i += 2){
        const Edge &e = Edges[i];
        if(dis[e.from] + e.dis == dis[e.to])ans[i >> 1] += to[e.from] * from[e.to],ans[i >> 1] %= mod;
    }
}
int main(){
    n = read(),m = read();
    for(int u,v,d,i = 1;i <= m;i++)
        u = read(),v = read(),d = read(),addedge(u,v,d),addedge(v,u,d);
    for(int i = 1;i <= n;i++)dijkstra(i);
    for(int i = 1;i <= m;i++)
        printf("%lld\n",ans[i]);
    return 0;
}