最短路计数问题

最短路

题意： 已知起点为1，求经过所有点的最短路径条数

分析： 首先题目肯定是个最短路问题，其次就是按照拓扑序求每个点的被最短路经过的次数

在分析最短路的时候，可能存在两种情况对应最短路：
1. $dist[j] > dist[t] + 1$,这一种对应的是第一次发现最短路的情况，即第一次找到中间点t，其可以作为从起点到j的最短路的桥梁，那么这个时候，经过j的最短路的条数与经过t的一致
2. $dist[j] = dist[t] + 1$,这一种对应的就是，找到一条与历史最短路一样的路径，那么过j点的最短路径总数为（当前过t的与过j的最短路径数之和）

通过题目例子解释：

解题代码如下：

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], e[N], ne[N], idx;
int dist[N], cnt[N];
bool v[N];

void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0,1});
    dist[1] = 0;
    cnt[1] = 1;

    while(q.size())
    {
        auto t = q.top();
        q.pop();

        int ver = t.second, dis = t.first;
        if(v[ver])  continue;
        v[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i] )
        {
            int j = e[i];
            if(dist[j] > dis + 1)
            {
                dist[j] = dis + 1;
                cnt[j] = cnt[ver];
                q.push({dist[j],j});
            }
            else if(dist[j] == dis + 1)
                cnt[j] = (cnt[j] + cnt[ver]) % 100003;
        }
    }
}

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int main()
{
    memset(dist, 0x3f, sizeof dist);
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a,b);
        add(b,a);
    }

    dijkstra();

    for(int i = 1; i <= n; i ++ )
        cout<<cnt[i]<<endl;

    return 0;
}