旅游规划(最短路问题)"/>
旅游规划(最短路问题)
题目描述
有了一张自驾旅游路线图,你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序,帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的,那么需要输出最便宜的一条路径。
输入描述
输入说明:输入数据的第1行给出4个正整数N、M、S、D,其中N(2<=N<=500)是城市的个数,顺便假设城市的编号为0~(N-1);M是高速公路的条数;S是出发地的城市编号;D是目的地的城市编号。随后的M行中,每行给出一条高速公路的信息,分别是:城市1、城市2、高速公路长度、收费额,中间用空格分开,数字均为整数且不超过500。输入保证解的存在。
输出描述
在一行里输出路径的长度和收费总额,数字间以空格分隔,输出结尾不能有多余空格。
样例
输入
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
输出
3 40
代码演示:
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int inf=1<<30;int n,m,s,d;
int dist[N]; //城市距出发地的距离
int vis[N]; //标记数组
int mp[N][N]; //地图标记,城市之间的连通
int spend[N]; //城市到出发地的花费
int cost[N][N];//城市之间的花费void dijkstra() {while(1) {int minn=inf; //每趟最短路径中最小的路径值int pos=-1; //得到的minn所对应的下标int mincost=-1;//最少花费for(int i=0; i<n; i++) { //寻找我们接下来要循环的点if(!vis[i] && dist[i]!=inf) {if(dist[i]<minn) {pos=i;minn=dist[i];mincost=spend[i];}else if(dist[i]==minn) {if(spend[i]<mincost) {pos=i;mincost=spend[i];}}}}if(pos==-1 || minn==inf) {break;}vis[pos]=1;for(int i=0; i<n; i++) {//int v=mp[pos][i];if(mp[pos][i]!=0 && vis[i]==0) { //更新 dist 和 spend 数组if(dist[i]>dist[pos]+mp[pos][i]) {dist[i]=dist[pos]+mp[pos][i];spend[i]=spend[pos]+cost[pos][i];}else if(dist[i]==dist[pos]+mp[pos][i]) {spend[i]=min(spend[i],spend[pos]+cost[pos][i]);}}}}
}int main()
{cin>>n>>m>>s>>d;for(int i=0; i<n; i++) {dist[i]=inf;}for(int i=0; i<m; i++) {int u,v,w,c;cin>>u>>v>>w>>c;mp[u][v]=w;mp[v][u]=w;cost[u][v]=c;cost[v][u]=c;}dist[s]=0;spend[s]=0;dijkstra();cout<<dist[d]<<" "<<spend[d];return 0;
}
更多推荐
旅游规划(最短路问题)
发布评论