【C++】ZZ2193-城市之路 解题精讲
2022/6/5 1:20:27
本文主要是介绍【C++】ZZ2193-城市之路 解题精讲,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【Horn Coding Studio】CPP编程专栏(狄克斯特拉-算法)
题目
题目描述
罗老师被邀请参加一个舞会,是在城市n,而罗老师当前所处的城市为1,附近还有很多城市2~n-1,有些城市之间没有直接相连的路,有些城市之间有直接相连的路,这些路都是双向的,当然也可能有多条。 现在给出直接相邻城市的路长度,罗老师想知道从城市1到城市n,最短多少距离。输入
输入n, m,表示n个城市和m条路; 接下来m行,每行a b c, 表示城市a与城市b有长度为c的路。输出
输出1到n的最短路。如果1到达不了n,就输出-1。样例输入 复制
5 5 1 2 20 2 3 30 3 4 20 4 5 20 1 5 100
样例输出 复制
90
知识点普及
无。
一点即通
十分简单的狄克斯特拉
不能单用邻接矩阵,而是要加上min函数,留下两个城市可以直接相连的最短路径,不然的话是WA的.
就是这句话!
我们需要定义一个结构体,但是!我们还需要再输入后排个序,不然………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………
因此,我们需要专门为她写一个以w为排序的代码,
bool
operator <(
const
qnode &r)
const
{
return
w>r.w;
}
另外由于这是一个双向图,我们的add函数需要运行两次,分别是:
a,b,c;
b,a,c;
接下来,就是万古不变的标准代码了!
代码
ZZOJ 100%AC,5052KB空间复杂度,13MS优秀时间复杂度。
Luogu OJ 没有这道题目
#include<bits/stdc++.h> #define INF 1e9 #define maxn 100005 using namespace std; int n,m; struct edge{ int u; int to; int w; int next; }edge[maxn]; int head[maxn],cnt; void add(int a,int b,int c){ edge[cnt].to=b; edge[cnt].w=c; edge[cnt].next=head[a]; head[a]=cnt; cnt++; }struct qnode{ int u,w; bool operator <(const qnode &r) const{ return w>r.w; } }; priority_queue<qnode> que; int dis[maxn],vis[maxn]; int DJ(int st,int ed){ for(int i=1;i<=n;i++){ dis[i]=INF; }dis[st]=0; que.push({st,0}); while(que.size()){ qnode tmp=que.top(); que.pop(); int u=tmp.u; if(vis[u]) continue; vis[u]=1; for(int i=head[u];i!=-1;i=edge[i].next){ int to=edge[i].to; if(dis[to]>dis[u]+edge[i].w){ dis[to]=dis[u]+edge[i].w; que.push({to,dis[to]}); } } }if(dis[ed]==INF) dis[ed]=-1; return dis[ed]; }int main(){ cin>>n>>m; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++){ int a,b,c; cin>>a>>b>>c; add(a,b,c); add(b,a,c); }cout<<DJ(1,n); return 0; } /************************************************************** User: FZK Language: C++ Result: 正确 Time:13 ms Memory:5052 kb ****************************************************************/
这篇关于【C++】ZZ2193-城市之路 解题精讲的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望