我是靠谱客的博主 平淡鞋垫,最近开发中收集的这篇文章主要介绍【最短路】洛谷P1144 最短路计数(注意过程取模问题),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目

LP1144

思路

正常最短路,检测到可以松弛覆盖最短路个数,检测到路径相等最短路个数加上即可。
本题注意过程取模问题,程序过程中就要及时取模,不要到了输出的时候再,不然鬼知道会不会爆。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#define _for(i,a,b) for(int i = a; i<b; i++)
#define _rep(i,a,b) for(int i = a; i<=b; i++)
using namespace std;
const int INF = 2000000 + 1000;
const int maxn = 1000000 + 10;
const int MOD = 100003;
int n, m, d[maxn], c[maxn];
bool done[maxn];
vector<int> G[maxn];
struct HeapNode {
int u, d;
bool operator < (const struct HeapNode& rhs) const {
return d>rhs.d;
}
HeapNode(int u, int d) :u(u), d(d) {};
};
void dijkstra(int s) {
priority_queue<HeapNode> q;
HeapNode first(s, 0);
q.push(first);
_rep(i, 1, n) d[i] = INF;
d[s] = 0; c[s] = 1;
while (!q.empty()) {
HeapNode now = q.top(); q.pop();
int u = now.u;
if (done[u]) continue;
done[u] = true;
_for(i, 0, G[u].size()) {
int v = G[u][i];
if (!done[v] && d[u] + 1 <= d[v]) {
if (d[u] + 1 < d[v]) {
d[v] = d[u] + 1;
c[v] = c[u];
HeapNode nn(v, d[v]);
q.push(nn);
}
else {
c[v] += c[u];
c[v] %= MOD;
}
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
int u, v;
_for(i, 0, m) {
scanf("%d%d", &u, &v);
if (u == v) continue;
G[u].push_back(v);
G[v].push_back(u);
}
dijkstra(1);
_rep(i, 1, n) printf("%dn", c[i]);
return 0;
}

最后

以上就是平淡鞋垫为你收集整理的【最短路】洛谷P1144 最短路计数(注意过程取模问题)的全部内容,希望文章能够帮你解决【最短路】洛谷P1144 最短路计数(注意过程取模问题)所遇到的程序开发问题。

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(67)

评论列表共有 0 条评论

立即
投稿
返回
顶部