最短路 ﹏ヽ暗。殇╰゛Y 2021-11-18 00:30 309阅读 0赞 Floyed [http://codevs.cn/problem/1077/][http_codevs.cn_problem_1077] #include<cstdio> const int N=105; typedef long long ll; ll dis[N][N]; int main(){ int n,q; scanf("%d",&n); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%lld",&dis[i][j]); for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j]; scanf("%d",&q); for(int i=1;i<=q;++i){ int u,v; scanf("%d%d",&u,&v); printf("%lld\n",dis[u][v]); } return 0; } 利用floyed求最小环 [http://acm.hdu.edu.cn/showproblem.php?pid=1599][http_acm.hdu.edu.cn_showproblem.php_pid_1599] 无向图 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=105,inf=1061109567; int dis[N][N],lb[N][N]; int main(){ int n,m,u,v,w; while(scanf("%d%d",&n,&m)!=EOF){ int ans=inf; memset(dis,0x3f,sizeof(dis)); memset(lb,0x3f,sizeof(lb)); while(m--){ scanf("%d%d%d",&u,&v,&w); lb[u][v]=lb[v][u]=dis[u][v]=dis[v][u]=min(lb[u][v],w); } for(int k=1;k<=n;++k){ for(int i=1;i<k;++i) if(lb[i][k]<inf) for(int j=i+1;j<k;++j) if(lb[j][k]<inf) ans=min(ans,lb[i][k]+lb[k][j]+dis[i][j]); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(lb[i][k]>0) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } if(ans==inf) printf("It's impossible.\n"); else printf("%d\n",ans); } return 0; } lg4779 [https://www.luogu.org/problemnew/show/P4779][https_www.luogu.org_problemnew_show_P4779] dijkstra #include<cstdio> #include<queue> #include<cstring> using namespace std; const int N=1e5+5; struct E{ int v,n,q; }e[N*5]; int fir[N],s,dis[N],ss; bool vis[N]; struct F{ int v,q; bool operator<(const F &a)const{ return q>a.q; } }st; priority_queue<F>dl; void add(int u,int v,int q){ e[++s].v=v; e[s].q=q; e[s].n=fir[u]; fir[u]=s; } int main(){ int n,m,u,v,q; scanf("%d%d%d",&n,&m,&st.v); while(m--){ scanf("%d%d%d",&u,&v,&q); add(u,v,q); } dl.push(st); for(int i=1;i<=n;++i) dis[i]=2147483647; dis[st.v]=0; while(!dl.empty()){ F t=dl.top();dl.pop(); if(vis[t.v]) continue; vis[t.v]=1;++ss; for(int i=fir[t.v];i;i=e[i].n) if(t.q+e[i].q<dis[e[i].v]){ dis[e[i].v]=e[i].q+t.q; if(!vis[e[i].v]) dl.push((F){e[i].v,dis[e[i].v]}); } } for(int i=1;i<=n;++i) printf("%d ",dis[i]); return 0; } lg3371 [https://www.luogu.org/problemnew/show/P3371][https_www.luogu.org_problemnew_show_P3371] spfa #include<cstdio> #include<queue> using namespace std; const int N=1e4+5,M=5e5+5; struct E{ int v,q,n; }e[M]; int fir[N],s,dis[N]; queue<int>dl; bool vis[N]; void add(int u,int v,int q){ e[++s].v=v; e[s].q=q; e[s].n=fir[u]; fir[u]=s; } int main(){ int n,m,st,u,v,q; scanf("%d%d%d",&n,&m,&st); while(m--){ scanf("%d%d%d",&u,&v,&q); add(u,v,q); } dl.push(st); vis[st]=1; for(int i=1;i<=n;++i) dis[i]=2147483647; dis[st]=0; while(!dl.empty()){ u=dl.front();dl.pop(); for(int i=fir[u];i;i=e[i].n) if(dis[u]+e[i].q<dis[e[i].v]){ dis[e[i].v]=dis[u]+e[i].q; if(!vis[e[i].v]){ vis[e[i].v]=1; dl.push(e[i].v); } } vis[u]=0; } for(int i=1;i<=n;++i) printf("%d ",dis[i]); return 0; } 转载于:https://www.cnblogs.com/bzmd/p/11119054.html [http_codevs.cn_problem_1077]: http://codevs.cn/problem/1077/ [http_acm.hdu.edu.cn_showproblem.php_pid_1599]: http://acm.hdu.edu.cn/showproblem.php?pid=1599 [https_www.luogu.org_problemnew_show_P4779]: https://www.luogu.org/problemnew/show/P4779 [https_www.luogu.org_problemnew_show_P3371]: https://www.luogu.org/problemnew/show/P3371
相关 最短路 <table> <tbody> <tr> <td> <h2>最短路</h2> <strong>Time Limit: 5000/1000 MS (Java/O 向右看齐/ 2024年02月18日 22:54/ 0 赞/ 61 阅读
相关 最短路 \[hdu 1599\] ([http://acm.hdu.edu.cn/showproblem.php?pid=1599][http_acm.hdu.edu.cn_showp 红太狼/ 2022年08月04日 08:28/ 0 赞/ 179 阅读
相关 C--最短路 Problem Description 给出一个带权无向图,包含n个点,m条边。求出s,e的最短路。保证最短路存在。 Input 多组输入。 对于每组数据。 以你之姓@/ 2022年07月12日 08:26/ 0 赞/ 138 阅读
相关 最短路 队列+松弛操作 读取队头顶点u,并将队头顶点u出队(记得消除标记);将与点u相连的所有点v进行松弛操作,如果能更新估计值(即令d\[v\]变小),那么就更新,另外,如果 忘是亡心i/ 2022年06月11日 04:06/ 0 赞/ 224 阅读
相关 最短路 一下模板均已通过HDUOJ 2544 程序设计竞赛队空间和时间复杂度要求都很高,所以朴素的Dijkstra[算法][Link 1]无论时间还是空间,效率都很低。 所以,一般 淡淡的烟草味﹌/ 2022年06月09日 04:28/ 0 赞/ 259 阅读
相关 最短路径(Dijkstra)-HDU 2544-最短路 最短路径(Dijkstra)-HDU 2544-最短路 -------------------- 题目链接: [最短路][Link 1] 亦凉/ 2022年05月14日 03:38/ 0 赞/ 232 阅读
相关 最短路 最短路 典型用途:交通网络的问题——从甲地到乙地之间是否有公路连通?在有多条通路的情况下,哪一条路最短? 交通网络用有向网来表示:顶点——表示城市,弧——表示两个城 淡淡的烟草味﹌/ 2022年03月18日 12:35/ 0 赞/ 275 阅读
相关 最短路 Floyed [http://codevs.cn/problem/1077/][http_codevs.cn_problem_1077] include<cstdi ﹏ヽ暗。殇╰゛Y/ 2021年11月18日 00:30/ 0 赞/ 310 阅读
相关 最短路 复习下图论算法 1. 邻接表的Dijkstra ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] / 冷不防/ 2021年11月02日 14:24/ 0 赞/ 467 阅读
相关 HDU 2544 最短路 最短路 时间限制:5000/1000 MS(Java / Others)内存限制:32768/32768 K(Java /其他) 提交总数:106773接受提交内容: 桃扇骨/ 2021年10月18日 08:20/ 0 赞/ 344 阅读
还没有评论,来说两句吧...