Luogu P1144 最短路计数

这道题先跑一个最短路，然后在用记忆化搜索搜出最短路条数。
开一个\(dis\)数组存最短路长度，开一个\(ans\)数组存答案。
搜到一个节点\(v\)，寻找它能到达的每个节点\(u\)，如果\(dis[u]+1==dis[v]\)，说明用最短路的走法走到\(u\)后，直接走到\(v\)就都是\(1\)到\(v\)的一条合法最短路。
此时，\(ans[v]=ans[u]+ans[v]\).
写记忆化搜索的时候，不要算过了还递归进去再返回，那样会TLE。
此外，把记忆化放进输出是一个很巧的方法。

#include<bits/stdc++.h>
#define N 1000010
#define M 2000010
#define MOD 100003
#define INF 0x3f3f3f3f

using namespace std;

int n,m,cnt;
int head[M],dis[N],ans[N];
bool vis[N];

struct node {
    int nxt,to;
}e[M*2];

void addEdge(int u,int v) {
    e[++cnt]=(node){head[u],v};
    head[u]=cnt;
    return;
}

void Read() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        addEdge(x,y);
        addEdge(y,x);
    }
    return;
}

void Init() {
    for(int i=2;i<=n;i++) {
        dis[i]=INF;
    }
    return;
}

void SPFA() {
    queue <int> q;
    ans[1]=1;
    q.push(1);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=e[i].nxt) {
            int v=e[i].to;
            if(dis[u]+1<dis[v]) {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return;
}

int Calc(int x) {
    for(int i=head[x];i;i=e[i].nxt) {
        int u=e[i].to;
        if(dis[u]+1==dis[x]) {
            ans[u]?ans[x]=(ans[x]+ans[u])%MOD:ans[x]=(ans[x]+Calc(u))%MOD;
        }
    }
    return ans[x];
}

void Print() {
    for(int i=1;i<=n;i++) {
        printf("%d\n",ans[i]?ans[i]:Calc(i));
    }
    return;
}

int main()
{
    Read();
    Init();
    SPFA();
    Print();
    return 0;
}

Luogu P1144 最短路计数

原文：https://www.cnblogs.com/luoshui-tianyi/p/11644633.html