洛谷 P1144 最短路计数#Spfa+DP

一道动态规划题，考虑下面两种情况。

对于u,v两点,cnt[i]为最短路径计数器

1.同一条最短路上的,则cnt[v]=cnt[u],继承前者状态
2.两条最短路遭遇,则cnt[v]+=cnt[u],路径数相加
对于多条最短路遭遇依旧可以认为是2.

分析完毕之后只要把计数器套到最短路模板里面就可以了。

考虑到Dijkstra算法要取最短边，即累计每条路的权值，至少要两个参数入优先队列，太麻烦了

直接用Spfa。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+1;
const int MOD=1e5+3;
const int MAX=INT_MAX>>1;

int n,m,x,y,dist[MAXN],ans[MAXN];
vector<int>e[MAXN];
bitset<MAXN>vis;
queue<int>q;
void spfa(){
    for(int i=2;i<=n;++i)
        dist[i]=MAX;
    ans[1]=1;
    q.push(1);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=false;
        for(auto i:e[now]){
            if(dist[now]+1<dist[i]){
                dist[i]=dist[now]+1;
                ans[i]=ans[now];
                if(!vis[i]){
                    vis[i]=true;
                    q.push(i);
                }
            }else if(dist[now]+1==dist[i]){
                ans[i]+=ans[now];
                ans[i]%=MOD;
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    spfa();
    for(int i=1;i<=n;++i)
        printf("%dn",ans[i]);
    return 0;
}

最后

以上就是心灵美皮卡丘为你收集整理的洛谷 P1144 最短路计数#Spfa+DP的全部内容，希望文章能够帮你解决洛谷 P1144 最短路计数#Spfa+DP所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。