luogu1144
2021/4/12 10:25:30
本文主要是介绍luogu1144,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给出一个N(1e6)个顶点M(2e6)条边的无向无权图,顶点编号为1−N。问从顶点1开始,到其他每个点的最短路有几条。
__________________________
dij求出每个点的最短路,如果最短路更新,则F[V]=F[U],如果刚好等于最短路,则f[v]+=f[u],最终输出答案。记得取模!
__________________________
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+10; 4 const int maxm=4e6+10; 5 struct edge 6 { 7 int u,v,w,nxt; 8 }e[maxm]; 9 int head[maxn],js; 10 void addage(int u,int v,int w) 11 { 12 e[++js].u=u;e[js].v=v;e[js].w=w; 13 e[js].nxt=head[u];head[u]=js; 14 } 15 int dis[maxn],f[maxn]; 16 bool vis[maxn]; 17 int n,m; 18 struct node 19 { 20 int dis,no; 21 bool operator < (const node &a)const 22 { 23 return dis>a.dis; 24 } 25 }; 26 priority_queue<node>q; 27 void dij() 28 { 29 memset(dis,0x3f,sizeof dis); 30 dis[1]=0;f[1]=1; 31 q.push((node){0,1}); 32 while(!q.empty()) 33 { 34 node uu=q.top();q.pop(); 35 int u=uu.no,d=uu.dis; 36 if(vis[u])continue; 37 vis[u]=1; 38 for(int i=head[u];i;i=e[i].nxt) 39 { 40 int v=e[i].v; 41 if(vis[v])continue; 42 if(dis[v]>dis[u]+e[i].w) 43 { 44 dis[v]=dis[u]+e[i].w; 45 f[v]=f[u]; 46 q.push((node){dis[v],v}); 47 } 48 else if(dis[v]==dis[u]+e[i].w) 49 { 50 f[v]=(f[u]+f[v])%100003; 51 } 52 } 53 } 54 } 55 int main() 56 { 57 scanf("%d%d",&n,&m); 58 for(int u,v,i=1;i<=m;++i) 59 { 60 scanf("%d%d",&u,&v); 61 addage(u,v,1);addage(v,u,1); 62 } 63 dij(); 64 for(int i=1;i<=n;++i)printf("%d\n",f[i]); 65 return 0; 66 }View Code
这篇关于luogu1144的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?