基础算法题——最短路计数（bfs遍历）

桃扇骨 2022-12-20 01:53 161阅读 0赞

#### [最短路计数][Link 1] ####

题目描述  
给出一个N个顶点M条边的无向无权图，顶点编号为 1-N 。问从顶点1开始，到其他每个点的最短路有几条。

输入格式  
第一行包含2个正整数 N, M，为图的顶点数与边数。

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

输出格式  
共 N 行，每行一个非负整数，第ii行输出从顶点 1 到顶点 i 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 ans mod 100003 后的结果即可。如果无法到达顶点 i 则输出0。

输入输出样例  
输入 \#1  
5 7  
1 2  
1 3  
2 4  
3 4  
2 3  
4 5  
4 5  
输出 \#1  
1  
1  
1  
2  
4  
说明/提示  
1到5的最短路有4条，分别为2条1-2-4-5和2条1-3-4-5  
（由于4-5的边有2条）。

对于20%的数据，N≤100；  
对于60%的数据，N≤1000；  
对于100%的数据，N<=1000000,M<=2000000。

--------------------

这道题还没有到做不出来的地步，那为什么我比赛的时候我做不出来呢？我想还是思路没理清（菜是原罪，哎）

#### 解题思路 ####

我们读题后看能发现题目中所谓的城市 1 到某城市的长度其实就是最少要从城市 1 经过多少个城市到达某城市。当然这里比较特殊需要考虑自环和重边，但是计算方法是不变的。

难点：最短路径与最短路径数的关系  
通过最短路径的变化，确定最短路径数的变化

--------------------

从城市 1 开始进行广度搜索，将 1 加入队列中。  
**情况一**：【城市 1 到 y 城市的最短路径】<【城市 1 到城市 x 的最短路径 + 城市 x 到 y 城市的最短路径】  
操作：  
①、【城市 1 到 y 城市的最短路径】 = 【城市 1 到城市 x 的最短路径 + 城市 x 到 y 城市的最短路径】  
②、将【城市 1 到 y 城市的最短路径数】 = 【城市 1 到城市 x 的最短路径数】  
③、将 y 城市放入队列中。

--------------------

**情况二**：【城市 1 到 y 城市的最短路径】>【城市 1 到城市 x 的最短路径 + 城市 x 到 y 城市的最短路径】  
不做任何操作

--------------------

**情况三**：【城市 1 到 y 城市的最短路径】=【城市 1 到城市 x 的最短路径 + 城市 x 到 y 城市的最短路径】  
操作：  
①、【城市 1 到 y 城市的最短路径数】 = 【城市 1 到城市 x 的最短路径数 + 城市 1 到 y 城市的最短路径数】

--------------------

从上面我们可以看到，我们需要维护的数组。  
min\_path 数组：城市 i 到 城市 1 的最短路径。  
path 数组：城市 i 到城市 1 的最短路径数。

--------------------

可能我表达的不是很清晰，代码可能描述得更明确…

#include<bits/stdc++.h>
    using namespace std;
    vector <int> u[100010];	//纪录关系
    int min_path[100010];	//每个城市的最短路径 
    int path[100010];		//每个城市最短路径的条数 
    const int mod = 100003;
    
    struct node{ 
    	int c;
    	int city;
    }Node, top;
    
    void bfs(){ 
    	queue <node> q;
    	q.push((node){ 1, 1});
    	min_path[1]=1;
    	path[1]=0;
    	while(!q.empty()){ 
    		top = q.front();
    		q.pop();
    		
    		for(int i=0; i<u[top.city].size(); i++){ 
    			int tmp = u[top.city][i];
    			if(top.c+1 < path[tmp]){ 		//存在更短路径 
    				path[tmp] = top.c+1;
    				min_path[tmp] = min_path[top.city];
    				Node.city = tmp;
    				Node.c = top.c+1;
    				q.push(Node);
    			}
    			else if(top.c+1 == path[tmp])	//有其他最短路径 
    				min_path[tmp] = (min_path[tmp]+min_path[top.city])%mod;
    		}
    	}
    	return;
    }
    
    int main(){ 
    	int n, m;
    	scanf("%d%d", &n, &m);
    	while(m--){ 
    		int x, y;
    		scanf("%d%d", &x, &y);
    		u[x].push_back(y);
    		u[y].push_back(x);
    	}
    	for(int i=1; i<=n; i++)
    		path[i] = 100010;
    	memset(min_path, 0, sizeof(min_path));
    	bfs();
    	for(int i=1; i<=n; i++){ 
    		printf("%d", min_path[i]);
    		if(i!=n) printf("\n");
    	}
    	return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P1144