06-2. 旅游规划（25）MOOC

本文主要是介绍06-2. 旅游规划（25）MOOC，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

06-2. 旅游规划（25）

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

输入格式说明：

输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2<=N<=500）是城市的个数，顺便假设城市的编号为0~(N-1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出格式说明：

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

思路：

加上了花费之后，除了更新路径时顺带更新花费之外，还要注意当u->v和w->v这两条路都可以达到最短路径的时候，需要把v的结点花费更新成这两种方式中最少的花费。既：c[e.to] = min(c[e.to], c[v] + e.cost);接下来就是普通的最短路算法了

/************************************************ Author: fisty* Created Time: 2015/1/17 18:56:05* File Name   : 06-2.cpp*********************************************** */
#include <iostream>
#include <cstring>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
#define Debug(x) cout << #x << " " << x <<endl
#define MAX_N 500
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef pair<int, int> P;
struct edge{int to;                 //下一个结点int cost;               //花费int dist;               //距离edge(int _to, int _cost, int _dist):to(_to), cost(_cost), dist(_dist){}
};
int N,M,S,D;                //结点个数，边数，出发点，终点
int c[MAX_N], d[MAX_N];     //每个顶点的最小花费与距离
vector<edge> G[MAX_N];      //构图
priority_queue<P, vector<P>, greater<P> > que;void dijkstra(){memset(d, 0x3f, sizeof(d));memset(c, 0x3f, sizeof(c));d[S] = 0;                         //出发点的距离初始化c[S] = 0;                         //出发点的花费初始化que.push(P(0, S));while(que.size()){P p = que.top(); que.pop();int v = p.second;if(d[v] < p.first) continue;for(int i = 0;i < G[v].size(); i++){edge &e = G[v][i];if(d[e.to] > d[v] + e.dist){//加上了花费d[e.to] = d[v] + e.dist;c[e.to] = c[v] + e.cost;que.push(P(d[e.to],e.to));}if(d[e.to] == d[v] + e.dist){//当出现重边的时候，需要判断一下花费是否有更小的可能c[e.to] = min(c[e.to], c[v] + e.cost);}}}printf("%d %d\n", d[D], c[D]);
}
int main() {//freopen("in.txt", "r", stdin);cin.tie(0);ios::sync_with_stdio(false);cin >> N >> M >> S >> D;for(int i = 0;i < M; i++){//a -> bint a, b, dist, cost;cin >> a >> b >> dist >> cost;//建图，无向图G[a].push_back(edge(b, cost, dist));G[b].push_back(edge(a, cost, dist));}dijkstra();return 0;
}

这篇关于06-2. 旅游规划（25）MOOC的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---