PAT-A 真题- 1030. Travel Plan（DFS筛选最优路径法）

原题干和原解答在这里：https://www.mmuaa.com/post/4146348c786b1cf1.html

下面这种方法显然比原来的解答复杂，而且耗费资源，但是是最不容易出错的一种方法，也是一个万能的解题模板，使用Dijkstra找出所有的最短路径，然后再由DFS遍历所有路径，找到最短的那一条。

代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 510
#define INF 0x3fffffff
int G[MAXN][MAXN], C[MAXN][MAXN];
bool visited[MAXN] = {false};
int MinDistance[MAXN];
int startP, endP;
int RoadCnt, CityCnt;
vector<vector<int> > pre;
vector<int> RealPath, tmpPath;

void init(){
    fill(MinDistance, MinDistance + MAXN, INF);
    fill(G[0], G[0] + MAXN * MAXN, INF);
    pre.resize(CityCnt);
}

void Dijkstra(int s){
    MinDistance[s] = 0;
    for(int i = 0; i < CityCnt; i++){
        //find the min-dis point in MinDistance
        int p = -1, MIN = INF;
        for(int j = 0; j < CityCnt; j++)
            if(visited[j] == false && MinDistance[j] < MIN)
                p = j, MIN = MinDistance[j];
        if(p == -1) return;

        //found
        visited[p] = true;
        //Use Point-p as medi-point to Update Point-j
        for(int j = 0; j < CityCnt; j++){
            if(visited[j] == false && G[p][j] != INF){
                //find a better way
                if(MinDistance[p] + G[p][j] < MinDistance[j]){
                    MinDistance[j] = MinDistance[p] + G[p][j];
                    pre[j].clear(); //Clear all pre
                    pre[j].push_back(p);
                }
                //if find a alike way
                else if(MinDistance[p] + G[p][j] == MinDistance[j])
                        pre[j].push_back(p);    //add a pre
            }
        }
        
    }
}

int minCost = INF;

void DFS(int v){
    tmpPath.push_back(v);   //让临时路径包含起点，便于计算总消费或遍历前驱
    if(v == startP){    //到达起点(遍历终点)
        int tmpCost = 0;    //计算该路径消费的容器
        for(int i = tmpPath.size()-1; i > 0; i--){  //遍历临时路径，累加消费
            int now = tmpPath[i], next = tmpPath[i-1];   //当前节点号和下一个节点号
            tmpCost += C[now][next];     //累加
        }
        if(tmpCost < minCost){      //如果发现了更小的消费
            minCost = tmpCost;      //更新最少消费值
            RealPath = tmpPath;     //更新路径
        }
    }
    else{   //没到达起点
        for(int i = 0; i < pre[v].size(); i++)  //遍历该节点ed所有前驱
            DFS(pre[v][i]);
    }
    tmpPath.pop_back(); //弹出节点，以便下次遍历
}

int main(){
    cin >> CityCnt >> RoadCnt >> startP >> endP;
    init();
    for(int i = 0; i < RoadCnt; i++){
        int _, __;
        cin >> _ >> __;
        cin >> G[_][__] >> C[_][__];
        G[__][_] = G[_][__], C[__][_] = C[_][__];
    }
    Dijkstra(startP);
    DFS(endP);
    for(int i = RealPath.size() - 1; i >= 0; i--)
        cout << RealPath[i] << " ";
    cout << MinDistance[endP] << " " << minCost << endl;
    return 0;
}