luogu1144 最短路计数

网友投稿 465 2022-11-09

luogu1144 最短路计数

luogu1144 最短路计数

​​ 题目描述 给出一个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。

#include#include#include#include#include#define inf 0x3f3f3f3f#define pa pairusing namespace std;#define N 1100000#define M 2200000#define mod 100003inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}map mp;int f[N],ans[N],h[N],n,e,num;bool flag[N];struct node{ int y,z,next;}data[M];void dijkstra(){ priority_queue,greater >q; memset(f,0x3f,sizeof(f));f[1]=0;q.push(make_pair(0,1));ans[1]=1; while (!q.empty()){ int x=q-().second;q.pop();if (flag[x]) continue;flag[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (f[x]+zq;memset(f,0x3f,sizeof(f));f[1]=0;q.push(1);ans[1]=1;flag[1]=1; while(!q.empty()){ int x=q.front();q.pop();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z; if (f[x]+z

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：数据
上一篇:luogu2668 斗地主
下一篇:poj2151 Check the difficulty of problems
相关文章

 发表评论

暂时没有评论，来抢沙发吧~