博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
COGS 2. 旅行计划
阅读量:5843 次
发布时间:2019-06-18

本文共 1633 字,大约阅读时间需要 5 分钟。

 

2. 旅行计划

★☆   输入文件:
djs.in   输出文件:
djs.out  
简单对比
时间限制:3 s   内存限制:128 MB

过暑假了,阿杜准备出行旅游,他已经查到了某些城市的两两之间的距离及可行路线(可行路线有方向),如下图所示。请你编程计算从阿杜所住城市到其它城市的最短路径以帮助阿杜制定旅行计划。

【输入格式】

输入由若干行组成,第一行有三个整数,$n(1≤n≤100)、m(1≤m≤n^2)、v(1≤m≤n)$;城市数,$m$城市间道路数,$v$是阿杜所住城市。第$2$至$m+1$行是每条路的信息,每行三个整数,为道路的起点、终点和两城市间距离。(城市从0开始编号)

【输出格式】

n组(按城市编号由小至大),每组三行

第一行:城市编号及一个冒号

第二行:path及一个冒号,后面是最短路径节点编号序列(编号间用一个空格隔开)

第三行:cost及一个冒号,后面是一个整数,表示路径距离

如果没有通路则输出 no

【输入样例】

6 8 00 2 100 4 300 5 1001 2 52 3 503 5 104 3 204 5 60

【输出样例】

0:no1:no2:path:0 2cost:103:path:0 4 3cost:504:path:0 4cost:305:path:0 4 3 5cost:60

AC代码:

#include
#include
#include
#define pir pair
using namespace std;const int N=1e5+10;struct node{ int v,w,next;}e[N<<1];int tot,head[N];int n,m,S,dis[N],qq[N];bool vis[N];void add(int x,int y,int z){ e[++tot].v=y; e[tot].w=z; e[tot].next=head[x]; head[x]=tot;}void dijkstra(){ priority_queue
,greater
>q; memset(dis,0x3f3f3f3f,sizeof dis); q.push(make_pair(dis[S]=0,S)); while(!q.empty()){ pir h=q.top();q.pop(); int x=h.second; if(vis[x]) continue; vis[x]=1; for(int v,w,i=head[x];i;i=e[i].next){ v=e[i].v;w=e[i].w; if(!vis[v]&&dis[v]>dis[x]+w){ q.push(make_pair(dis[v]=dis[x]+w,v)); qq[v]=x; } } } }void out(int x){ if(qq[x]==-1) return ; out(qq[x]); printf("%d ",x);}int main(){ freopen("djs.in","r",stdin); freopen("djs.out","w",stdout); memset(qq,-1,sizeof qq); scanf("%d%d%d",&n,&m,&S); for(int i=1,x,y,z;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y,z); } dijkstra(); for(int i=0;i

 

转载于:https://www.cnblogs.com/shenben/p/6045921.html

你可能感兴趣的文章
内存中压缩图片
查看>>
Android命令Monkey压力测试,详解
查看>>
log4j2 mybatis 显示 sql 和 结果集
查看>>
Linux——JDK的部署
查看>>
设计模式-Factory Method Pattern
查看>>
VS2010下Boost1.55.0配置
查看>>
负载均衡(LB)集群 dr
查看>>
Entity Framework 批量插入
查看>>
hierarchyviewer
查看>>
linux 文件系统的管理 (硬盘)
查看>>
微服务框架开发(二)—扩展spring schema
查看>>
(转)直接拿来用!最火的iOS开源项目(一)
查看>>
java8新特性stream深入解析
查看>>
Linux manjaro系统安装后无法连接wifi,解决方案
查看>>
关于我的知识星球服务
查看>>
前端每隔几秒发送一个请求
查看>>
div+css+js 树形菜单
查看>>
javax.jdo.option.ConnectionURL配置的问题
查看>>
ubuntu 开启 apache mod_rewrite
查看>>
android EventBus 3.0 混淆配置
查看>>