最短路计数(Shortest Path Count)

2024-02-05 10:58

本文主要是介绍最短路计数(Shortest Path Count),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

By Stockholm

最短路计数(Shortest Path Count)

来源:Luogu P1144
题目描述
给出一个 N 个顶点 M 条边的无向无权图,顶点编号为 1~N。问从
顶点 1 开始,到其他每个点的最短路有几条。
输入输出格式
输入格式:
输入第一行包含 2 个正整数 N,M,为图的顶点数与边数。
接下来 M 行,每行两个正整数 x, y,表示有一条顶点 x 连向顶点 y
的边,请注意可能有自环与重边。
输出格式:
输出包括 N 行,每行一个非负整数,第 i 行输出从顶点 1 到顶点 i 有
多少条不同的最短路,由于答案有可能会很大,你只需要输出 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。

思路

这个题用 SPFA 做,但是需要加一个计数操作,注意最后结果取模,以及如果一样的长度, 就需要在原来的基础上加上上一个节点累加器
中的记录数,SPFA 最好带上 SLF,这样快一些。

代码(C++)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<deque>
using namespace std;
int i,j,m,n;
int head[1000001];
int us[1000001];
int t[1000001];int dis[1000001];
struct node
{
int yy;
struct node *nxt;
}a[4000005];
int r()
{
int aans=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
{
aans*=10;
aans+=ch-'0';
ch=getchar();
}
return aans;
}int spfa(int x)
{
us[x]=1;
deque<int>q;
dis[x]=0;
q.push_front(x);
struct node *p;
while(!q.empty())
{
x=q.front();
p=&a[head[x]];
us[x]=0;
q.pop_front();
while(p->yy!=0)
{
if(dis[x]+1<dis[p->yy])
{
t[p->yy]=t[x]%100003;
dis[p->yy]=dis[x]+1;if(!us[p->yy])
{
if(q.empty()||dis[q.front()]>dis[p->yy])
q.push_front(p->yy);
else
q.push_back(p->yy);
us[p->yy]=1;
}
}
else if(dis[x]+1==dis[p->yy])
{t[p->yy]+=t[x];
t[p->yy]%=100003;}
p=p->nxt;
}
}
}
int main()
{
n=r(),m=r();
int x,y;for(i=1;i<=m;i++)
{
x=r(),y=r();
a[2*i-1].yy=y;
a[2*i-1].nxt=&a[head[x]];
head[x]=2*i-1;
a[2*i].yy=x;
a[2*i].nxt=&a[head[y]];
head[y]=2*i;
}
memset(dis,0x7f7f7f7f,sizeof(dis));
t[1]=1;
spfa(1);
for(i=1;i<=n;i++)
if(dis[i]!=0x7f7f7f7f)
cout<<t[i]<<endl;
else
cout<<0<<endl;
return 0;
}

这里写图片描述

这篇关于最短路计数(Shortest Path Count)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/680696

相关文章

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

poj 3159 (spfa差分约束最短路) poj 1201

poj 3159: 题意: 每次给出b比a多不多于c个糖果,求n最多比1多多少个糖果。 解析: 差分约束。 这个博客讲差分约束讲的比较好: http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码: #include <iostream>#include <cstdio>#i

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

poj 3255 次短路(第k短路) A* + spfa 或 dijkstra

题意: 给一张无向图,求从1到n的次短路。 解析: A* + spfa 或者 dijkstra。 详解见上一题:http://blog.csdn.net/u013508213/article/details/46400189 本题,spfa中,stack超时,queue的效率最高,priority_queue次之。 代码: #include <iostream>#i

poj 2449 第k短路 A* + spfa

poj 2449: 题意: 给一张有向图,求第k短路。 解析: A* + spfa。 一下转自:http://blog.csdn.net/mbxc816/article/details/7197228 “描述一下怎样用启发式搜索来解决K短路。 首先我们知道A*的基础公式:f(x)=g(x)+h(x);对h(x)进行设计,根据定义h(x)为当前的x点到目标点t所需要的实际距

poj 3259 最短路负环

John的农场里N块地,M条路连接两块地,W个虫洞,虫洞是一条单向路,会在你离开之前把你传送到目的地,就是当你过去的时候时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来,看到了离开之前的自己。简化下,就是看图中有没有负权环。有的话就是可以,没有的话就是不可以了。 import java.io.BufferedReader;import java.io.InputStream;

POJ1724最短路

n个点,拥有总的价值money m条边(u,v,len ,cost),长度len,代价cost 求不超过money的代价条件下最短路。 public class Main {public static void main(String[] args) {new Task().solve();}}class Task {InputReader in = new InputReader

【AcWing】851. 求最短路

spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新,但是每一次迭代的话我不一定每条边都会更新,SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话,那么一定是dist[a]变小了,只有a变小了,a的后继(b)才会变小。 用宽搜来做优化,用一个队列,队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁,我再拿