首页 > 代码库 > COGS 2. 旅行计划
COGS 2. 旅行计划
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<cstdio>#include<cstring>#include<queue>#define pir pair<int,int>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<pir,vector<pir>,greater<pir> >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<n;i++){ if(i==S) printf("%d:\nno\n",S); else if(dis[i]==0x3f3f3f3f) printf("%d:\nno\n",i); else{ printf("%d:\n",i); printf("path:%d ",S);out(i);putchar(‘\n‘); printf("cost:%d\n",dis[i]); } } fclose(stdin); fclose(stdout); return 0;}
COGS 2. 旅行计划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。