PAT 1030 Travel Plan (30分) Dijstra +Dfs

标签：iostream   must   起点   out   uniq   one   tput   clear   path   

题目

A traveler‘s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:
Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (≤500) is the number of cities (and hence the cities are numbered from 0 to N?1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

City1 City2 Distance Cost
where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:
For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input:
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
Sample Output:
0 2 3 3 40

题目解读

给出由n个节点和m条边组成的无向图，给出m条边的距离和代价，给定起点和终点，要求输出从起点到终点的最短路径、最短距离、以及最小代价。

这个题，本质上和 PAT 1018 Public Bike Management 是一样的，无非就是在Dijstra求最短距离的过程中保存最短路径上的前驱，再跟据DFS结合前驱得到全部最短路径，在此过程中计算每一条最短路径的代价，选出最小的那条。

思路分析

• 首先，遇到最短路径，肯定是Dijstra，但题目说了，可能会有多条最短路径，我们要找到全部路径怎么办？把每一个路径都保存下来吗？可以，但没必要。我们只需要记录最短路径上每个节点的直接前驱就可以了，而这个，在Dijstra算法中，只需要在更新过程中（d[v] = d[u] + e[u][v]）加上一条语句就可以了（prev[v].push_back(u)），非常简单。如果它有多个最短路径，那么它就有多个直接前驱，因此，每个节点都应该有一个vector来保存它的全部最短路径的直接前驱，最终，就是需要一个vector数组。
• 找到最短路径显然是不够的，我们还要进行选择，选择那一条最短路径的代价最小。所以，我们要遍历全部最短路径，于是dfs就出场了，因为我们保存的是节点的全部直接前驱，所以需要从终点往起点去寻找。每一次从终点找到起点的路径都是一条最短路径，这其实就是一个DFS，计算这条路径的代价，如果更小，则更新最小代价并选择这条路径。
• 所以，总的来说就是，Dijstra找到全部最短路径，dfs遍历每个最短路径并找到代价最小的那个。

满分代码

注释写的比较详细，思路说的太多反而容易迷糊，建议多看看dfs，这个还是很常用的。

#include 
#include 
#include 
#include 
using namespace std;

// n个顶点m条边,s是起点,d是终点
int n, m, s, d;
// edge保存两个点之间的距离,min_dis保存起点到每个顶点的最短距离,cost保存每两个点之间的代价
int edge[501][501], min_dis[501], cost[501][501];
// 保存每个顶点在 从起点到它的全部最短路径上 的直接前驱
// 假如 0 1 2 4 和 0 3 4都是从0到4的直接前驱,那么pre[4] = {2,3}
vector pre[501];
// dijstra求最短距离时的划分
bool visited[501];

// temppath用于保存起点到终点的全部最短路径中的其中一个,path保存代价最小的最短路径
vector temppath, path;
// 最小代价
int min_cost = INT_MAX;

// 深度优先遍历,对于从起点到终点的全部最短路径,算出每个路径的代价,选择代价最小的那条
void dfs(int v) {
    // 当前节点入当前路径
    temppath.push_back(v);
    // 如果达到起点(我们是根据保存的前缀从后往前搜索)
    if (v == s) {
        // temppath里保存了一条完整的路径,并且是从终点到起点
        int tempcost = 0;
        // 计算这条路上的代价,
        for (int i = temppath.size() - 1; i >= 1; --i) {
            tempcost += cost[temppath[i]][temppath[i - 1]];
        }
        // 如果选择这条最短路径的代价更小
        if (tempcost > n >> m >> s >> d;

    int f, t, dd, cc;
    // 输入n条边的距离和代价
    while (m-- > 0) {
        cin >> f >> t >> dd >> cc;
        edge[f][t] = edge[t][f] = dd;
        cost[f][t] = cost[t][f] = cc;
    }
    // dijstra初始化,到起点的距离为0
    min_dis[s] = 0;
    // dijstra
    for (int i = 0; i = 0; --i) {
        cout 

PAT 1030 Travel Plan (30分) Dijstra +Dfs

标签：iostream   must   起点   out   uniq   one   tput   clear   path   

原文地址：https://www.cnblogs.com/codervivi/p/12975145.html