【洛谷】P1144 最短路计数

48 阅读 0 评论 32 点赞

我是靠谱客的博主眼睛大宝马，最近开发中收集的这篇文章主要介绍【洛谷】P1144 最短路计数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

因为无向无权，实际上最短路径长度=该点在bfs搜索树的深度

dfs似乎没法解决自环，会一直不断循环

当然用Dijkstra做也可以

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

struct d_node{
    int v,w;
    friend bool operator < (const d_node &d1,const d_node &d2){
        return d1.w>d2.w;
    }
};

int nv,ne;
#define maxn 1000010
#define num_mod 100003
vector<int> G[maxn];
int num[maxn];
int depth[maxn];//因为边权为1,该点最短路其实就是该点在bfs搜索树的深度
int vis[maxn];
void bfs(int s){//标准bfs
    queue<int> q;
    q.push(s);
    depth[s]=0,num[s]=1,vis[s]=1;
    while(!q.empty()){
        int tmp=q.front();
        q.pop();

        for(int j=0;j<G[tmp].size();j++){
            int v=G[tmp][j];
            if(!vis[v]){
                vis[v]=1;
                depth[v]=depth[tmp]+1;//树高就是最短路长度
                q.push(v);
            }
            if(depth[v]==depth[tmp]+1){//无论访问没访问,都在这里更新了num[]
                num[v]+=num[tmp];
                num[v]%=num_mod;
            }
        }
    } 
}


int main(){
    scanf("%d %d",&nv,&ne);

    int t1,t2,tw;
    for(int i=0;i<ne;i++){
        scanf("%d %d",&t1,&t2);
        G[t1].push_back(t2);
        G[t2].push_back(t1);//无向
    }
    
    bfs(1);
    
    for(int i=1;i<=nv;i++){
        printf("%dn",num[i]);
    }
    
    return 0;
}

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

struct d_node{
    int v,w;
    friend bool operator < (const d_node &d1,const d_node &d2){
        return d1.w>d2.w;
    }
};

int nv,ne;
#define maxn 1000010
#define num_mod 100003
vector<int> G[maxn];

int collected[maxn];
int dist[maxn],num[maxn];
priority_queue<d_node> h;
void dijkstra(int s){
    fill(dist+1,dist+maxn,INT_MAX);
    dist[s]=0,num[s]=1;
    h.push(d_node{s,0});
    while(!h.empty()){
        d_node minNode=h.top();
        h.pop();
        if(collected[minNode.v]) continue;
        collected[minNode.v]=1;
        for(int j=0;j<G[minNode.v].size();j++){
            int v=G[minNode.v][j];
            if(!collected[v]){
                if(dist[v]>minNode.w+1){
                    dist[v]=minNode.w+1;
                    h.push(d_node{v,dist[v]});
                    num[v]=num[minNode.v];
                }else if(dist[v]==minNode.w+1){
                    num[v]+=num[minNode.v];
                    num[v]%=num_mod;
                }
            }
        }
    }
}

int main(){
    scanf("%d %d",&nv,&ne);

    int t1,t2,tw;
    for(int i=0;i<ne;i++){
        scanf("%d %d",&t1,&t2);
        G[t1].push_back(t2);
        G[t2].push_back(t1);//无向
    }
    
    dijkstra(1);
    for(int i=1;i<=nv;i++){
        printf("%dn",num[i]);
    }
    
    return 0;
}