洛谷 P1144 最短路计数（Dijkstra+堆优化）

桃扇骨 2023-07-10 14:26 19阅读 0赞

### 没有堆优化会超时，只有60分。 ###

## 题目描述 ##

给出一个NNN个顶点MMM条边的无向无权图，顶点编号为1−N1-N1−N。问从顶点111开始，到其他每个点的最短路有几条。

## 输入格式 ##

第一行包含222个正整数N,MN,MN,M，为图的顶点数与边数。

接下来MMM行，每行222个正整数x,yx,yx,y，表示有一条顶点xxx连向顶点yyy的边，请注意可能有自环与重边。

## 输出格式 ##

共NNN行，每行一个非负整数，第iii行输出从顶点111到顶点iii有多少条不同的最短路，由于答案有可能会很大，你只需要输出ans mod 100003 ans \\bmod 100003ansmod100003后的结果即可。如果无法到达顶点iii则输出000。

## 输入输出样例 ##

**输入 \#1**

5 7
    1 2
    1 3
    2 4
    3 4
    2 3
    4 5
    4 5

**输出 \#1**

1
    1
    1
    2
    4

## 说明/提示 ##

111到555的最短路有444条，分别为222条1−2−4−51-2-4-51−2−4−5和222条1−3−4−51-3-4-51−3−4−5（由于4−54-54−5的边有222条）。

对于20%20\\%20%的数据，N≤100N ≤ 100N≤100；

对于60%60\\%60%的数据，N≤1000N ≤ 1000N≤1000；

对于100%100\\%100%的数据，N<=1000000,M<=2000000N<=1000000,M<=2000000N<=1000000,M<=2000000。

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    #include<map>
    #include<unordered_map>
    #include<set>
    #include<sstream>
    using namespace std;
    const int MAXN = 1000002; 
    const int INF = 10000000;
    
    struct Node{
    	int u;   //节点编号 
    	int dis; //dis[u] 
    	//构造函数 
    	Node(int u,int dis){
    		this->u = u;
    		this->dis = dis; 
    	}
    	//定义比较大小的方式是：dis越小的越大，因为是最大堆，所以dis越小的越靠近堆顶部。 
    	bool operator<(const Node &node) const {  
    		return this->dis > node.dis;
    	}
    };
    
    vector<int> adj[MAXN];  //邻接表 
    int dis[MAXN];
    bool vis[MAXN] = {false}; 
    priority_queue<Node> choose;  //用priority_queue模拟堆优化（priority_queue的底层实现是最大堆） 
    int num[MAXN]; //记录到u的最短路径条数为num[u] 
    
    void Dijkstra(int s,int n){
    	fill(dis,dis+n+1,INF);
    	dis[s] = 0;
    	num[s] = 1;
    	choose.push(Node(s,dis[s]));  //堆插入 
    	for(int i=1;i<=n;i++){
    		int u = -1;
    		/*
    		** 讲原来的for循环查找最小距离改成从堆中弹出第一个元素 
    		*/
    		if(!choose.empty()){
    			const Node &node = choose.top();   //堆弹出（不删除） 
    			u = node.u;
    			choose.pop();	// 堆弹出（删除） 
    		}
    		if(u == -1){
    			return ;
    		}
    		vis[u] = true;
    		for(auto it=adj[u].begin();it!=adj[u].end();it++){
    			int v = *it;
    			if(!vis[v]){
    				if(dis[v] > dis[u] + 1){
    					dis[v] = dis[u] + 1;
    					/*
    					** 堆中会有多个v节点对应的dis[v]，但是我们会弹出最小的那个。 
    					*/
    					choose.push(Node(v,dis[v]));//堆插入 
    					num[v] = num[u];
    				}else if(dis[v] == dis[u] + 1){
    					num[v] = (num[v] + num[u]) % 100003;
    				}
    			}
    		}
    	}
    }
    
    int main(){
    	int n,m;
    	int u,v;
    	cin>>n>>m;
    	while(m--){
    		cin>>u>>v;
    		adj[u].push_back(v);
    		adj[v].push_back(u);
    	}
    	Dijkstra(1,n);
    	for(int i=1;i<=n;i++){
    		if(dis[i]!=INF){
    			cout<<num[i]<<endl;
    		}else{
    			cout<<"0"<<endl;
    		}
    	}
    	return 0; 
    }

我在做另一个题的时候，发现了这个堆优化的一些问题。上面的代码中有一块写错了：请看代码块2（下面第二个代码块）。

在这个题目中这样写没错（可能是样例也没考虑到一种特殊情况），但是是存在问题的，因为现在我们的priority\_queue队列中会有多个重复的节点，因为当我们发现某个点的dis被改变时，我们把这个点直接重复插入了priority\_queue中，并没有弹出之前的原数据。如下图（代码块1）所示：

所以我们需要改一下代码块2，改成代码块3。也就是在弹出节点的时候判断一下这个点访问过没有，是不是已经访问过的节点的重复，如果是的话就再弹一个，再判断。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70][]

代码块1**（上图）**

if(!choose.empty()){
        const Node &node = choose.top();   //堆弹出（不删除） 
        u = node.u;
        choose.pop();	// 堆弹出（删除） 
    }

代码块2**（上图）**

int u = -1;
    do{
        if(!choose.empty()){
            const Node node = choose.top();
            u = node.v;
            choose.pop();
        }	
    }while(vis[u]);
    vis[u] = true;

代码块3**（上图）**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200308204932882.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTE1Njg2,size_16,color_FFFFFF,t_70