luogu 1144 最短路计数 (堆优化Dijkstra)

本文主要是介绍luogu 1144 最短路计数 (堆优化Dijkstra)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

输入输出格式

输入格式：

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

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

 

输出格式：

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

题目链接：https://www.luogu.org/problemnew/show/P1144

题目分析：由于用链式前向星存边，对重边无需做特殊判断

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
int const MAXN = 1000005;
int const MAXM = 2000005;
int const INF = 0x3ffffff;
int const MOD = 100003;
int n, m, dis[MAXN], num[MAXN];
int cnt, head[MAXN];
bool vis[MAXN];
map<pair<int, int>, int> mp;
map<pair<int, int>, int>:: iterator it;struct EDGE {int to, w, nxt;
}e[MAXM << 1];void Init() {cnt = 0;memset(head, -1, sizeof(head));memset(vis, false, sizeof(vis));
}void Add(int u, int v) {e[cnt].to = v;e[cnt].w = 1;e[cnt].nxt = head[u];head[u] = cnt++;
}void HeapDijkstra(int v0) {priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > q;for (int i = 1; i <= n; i++) {dis[i] = INF;}dis[v0] = 0;num[v0] = 1;q.push(make_pair(0, v0));while (!q.empty()) {int u = q.top().second;q.pop();if (!vis[u]) {vis[u] = true;for (int i = head[u]; i != -1; i = e[i].nxt) {int v = e[i].to;if (dis[v] == dis[u] + e[i].w) {num[v] += num[u];num[v] %= MOD;} else if (dis[v] > dis[u] + e[i].w) {dis[v] = dis[u] + e[i].w;q.push(make_pair(dis[v], v));num[v] = num[u];}}}}
}int main() {Init();scanf("%d %d", &n, &m);int u, v;for (int i = 0; i < m; i++) {scanf("%d %d", &u, &v);if (u == v) {continue;}Add(u, v);Add(v, u);}HeapDijkstra(1);for (int i = 1; i <= n; i++) {printf("%d\n", num[i] % MOD);}
}

 

这篇关于luogu 1144 最短路计数 (堆优化Dijkstra)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---