最短路计数

题目描述：

n个点m条边的无向无权图，问从顶点1开始，到其他每个点的最短路有几条

思路：

最短路计数首先要满足的条件是不能存在权值为0的环，如果存在，则能经过这个环的点的最短路的数量就是无穷大了

把图抽象成一个拓扑树

BFS可以做，因为权值是1，且BFS能保证点只入队一次且出队一次，是一个拓扑树，它可以保证被更新的点的父节点一定已经是最短距离了，并且这个父节点的最短路的条数已经被完全更新过了

迪杰斯特拉也可以做，因为他每个点只出队一次，被标记过后入队也不会再更新，也相当于只入队一次，也是一个拓扑树

如果图中不存在负权边，我们就可以使用BFS或者迪杰斯特拉来计算

代码如下：

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 100003
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 400000 + 50
int n, m;

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dis[MAX];
bool vis[MAX];
int ans[MAX];
void dijkstra(){
    mem(dis, inf);
    priority_queue<pii, vector<pii>, greater<pii>>q;
    q.push(m_p(0, 1));dis[1] = 0;ans[1] = 1;
    while (!q.empty()) {
        auto [d, u] = q.top();q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + 1){
                ans[v] = ans[u];
                dis[v] = dis[u] + 1;
                q.push(m_p(dis[v], v));
            }
            else if(dis[v] == dis[u] + 1){
                ans[v] = (ans[v] + ans[u]) % mod;
            }
        }
    }
    for(int i = 1; i <= n; ++i)cout << ans[i] << endl;
}


void work(){
    cin >> n >> m;
    for(int i = 1, a, b; i <= m; ++i){
        cin >> a >> b;
        add(a, b);add(b, a);
    }
    dijkstra();
}


int main(){
    io;
    work();
    return 0;
}

但如果图中存在负权边，则不可以用上述两种方法，只能用SPFA

但问题是SPFA进行的过程中不能保证每时每刻的图都是正确的拓扑树

所以不可以边跑最短路边计算最短路数量

但是我们可以先跑一边SPFA，计算出每个点的最短路，然后遍历所有边，找出哪些边满足dis[v] = dis[u] + 1,即找出哪些边在拓扑树上，然后再建图使用BFS遍历这个拓扑树来计算答案

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 100003
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 400000 + 50
int n, m, k;
vector<pii>v;

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

bool vis[MAX];
int dis[MAX];
void SPFA(){
    queue<int>q;
    mem(dis, inf);
    q.push(1);dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] > dis[u] + 1){
                dis[v] = dis[u] + 1;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

int num[MAX];
void bfs(){
    queue<int>q;
    mem(vis, 0);
    q.push(1);num[1] = 1;
    while (!q.empty()) {
        int u = q.front();q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            num[v] = (num[v] + num[u]) % mod;
            q.push(v);
        }
    }
    for(int i = 1; i <= n; ++i)cout << num[i] << endl;
}

void work(){
    cin >> n >> m;
    for(int i = 1, a, b; i <= m; ++i){
        cin >> a >> b;
        v.push_back(m_p(a, b));
        add(a, b);add(b, a);
    }
    SPFA();
    tot = 0;
    mem(head, 0);
    for(auto [a, b] : v){
        if(dis[b] == dis[a] + 1){
            add(a, b);
        }
        else if(dis[a] == dis[b] + 1){
            add(b, a);
        }
    }
    bfs();
}


int main(){
    io;
    work();
    return 0;
}