首页 > 代码库 > P1144 最短路计数
P1144 最短路计数
题目描述
给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。
输入输出格式
输入格式：输入第一行包含2个正整数N，M，为图的顶点数与边数。
接下来M行，每行两个正整数x, y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式：输出包括N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出mod 100003后的结果即可。如果无法到达顶点i则输出0。
输入输出样例
输入样例#1：
5 71 21 32 43 42 34 54 5
输出样例#1：
11124
说明
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 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 void read(int & n) 8 { 9 char c=‘+‘;int x=0; 10 while(c<‘0‘||c>‘9‘)c=getchar(); 11 while(c>=‘0‘&&c<=‘9‘) 12 { 13 x=x*10+c-48; 14 c=getchar(); 15 } 16 n=x; 17 } 18 const int MAXN=1000401; 19 const int maxn=0x7fffff; 20 int tot[MAXN]; 21 struct node 22 { 23 int u,v,w,nxt; 24 }edge[MAXN*4]; 25 int head[MAXN]; 26 int num=1; 27 int n,m; 28 int dis[MAXN]; 29 int vis[MAXN]; 30 struct dian 31 { 32 int bh; 33 int jl; 34 }a[MAXN]; 35 void add(int x,int y) 36 { 37 edge[num].u=x; 38 edge[num].v=y; 39 edge[num].w=1; 40 edge[num].nxt=head[x]; 41 head[x]=num++; 42 } 43 bool operator <(dian a,dian b){return a.jl>b.jl;} 44 void dj() 45 { 46 47 priority_queue<dian>q; 48 dis[1]=0; 49 vis[1]=1; 50 tot[1]=1; 51 dian now; 52 now.bh=1; 53 now.jl=0; 54 q.push(now); 55 while(q.size()!=0) 56 { 57 dian p=q.top(); 58 q.pop(); 59 vis[p.bh]=0; 60 if(dis[p.bh]!=p.jl)continue; 61 for(int i=head[p.bh];i!=-1;i=edge[i].nxt) 62 { 63 int will=edge[i].v; 64 if(dis[will]==dis[p.bh]+edge[i].w) 65 { 66 tot[will]=(tot[p.bh]+tot[will])%100003; 67 } 68 if(dis[will]>dis[p.bh]+edge[i].w) 69 { 70 dis[will]=dis[p.bh]+edge[i].w; 71 tot[will]=(tot[p.bh])%100003; 72 if(vis[will]==0) 73 { 74 dian nxt; 75 nxt.bh=will; 76 nxt.jl=dis[will]; 77 q.push(nxt); 78 vis[will]=1; 79 } 80 } 81 } 82 } 83 84 } 85 int main() 86 { 87 read(n);read(m); 88 for(int i=1;i<=n;i++) 89 dis[i]=maxn,head[i]=-1; 90 for(int i=1;i<=m;i++) 91 { 92 int x,y; 93 read(x);read(y); 94 add(x,y);add(y,x); 95 } 96 dj(); 97 for(int i=1;i<=n;i++) 98 printf("%d\n",tot[i]); 99 return 0;100 }
P1144 最短路计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。