旅游规划（最短路问题）

旅游规划（最短路问题）"/>

旅游规划（最短路问题）

题目描述

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入描述

输入说明：输入数据的第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;
}