题目

PAT的题库偏模板。这道题用的思路就是正常的dijkstra+dfs的思路。
一般遇到第二标尺第三标尺需要保存路径的题目，都是用pre数组的办法。

简单讲解

一般来说这种题目，它的最短路径不是只有唯一一条，而是有多条。并且权值不单一，可能是多种权值作为衡量的标准。

准确点说的话就是：在满足某个权值最小之后，再满足第二个权值最小or最大，再满足第三个权值最小or最大那个样子。(这里的权值标尺不一定是线，可能是点)。因此解决这类问题的通解是将dijkstra算法算出的所有最短路径都保存下来。

如果题目比较简单，可以直接根据题目做调整，不需要完全按照这个模型去做。这只是个通用的模型。dfs函数写起来还是很麻烦的。

这里保存的办法还是很简单粗暴的。建立一个pre数组，数组里每个数据都是一个链表。而pre数组的下标代表的是图中点的编号。数组中的链表，存放的也是图中的编号，和数组下标的关系是链表的编号代表的点 —> 数组的下标代表的点。

举个例子：

a ---> c

b ---> c
那么，pre[c]的那个链表存放的就是a, b，从a，b可以到达c，所以c的pre里存着a和b

看明白了例子，就知道大概是个什么思路了。dfs从终点开始，查看pre数组里存放的点，再对每个点做一遍dfs。递归的出口就是，pre数组的链表为空,说明到达起点，历遍了一整条最短路径，然后在递归的出口处理题目的要求即可。

样例

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

代码实现

// Acwing1507 旅行计划

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#include <map>

using namespace std;

typedef pair<int, int> PII;

map<PII, int> cost_map;

const int N = 1e5 + 10;

int dist[N];
bool st[N];
int e[N], w[N], ne[N], h[N], idx;

int s, d;

vector<vector<int>> pre(N);

void add (int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h [a] = idx ++; 
}

void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    priority_queue <PII, vector<PII>, greater<PII>> heap;
    heap.push({0, s});
    while(heap.size()) {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
                pre[j].clear();
                pre[j].push_back(ver);
            } else if (dist[j] == dist[ver] + w[i]) {
                pre[j].push_back(ver);
            }
        }
    }
}

vector<int> ans, tmp;
int min_cost = 0x3f3f3f3f;

void dfs(int idx, int cost) {
    if (pre[idx].empty()) {
        if (min_cost > cost) {
            min_cost = cost;
            ans = tmp;
        }
        return;
    }
    for (auto i : pre[idx]) {
        tmp.push_back(i);
        dfs(i, cost + cost_map[{idx, i}]);
        tmp.pop_back();
    }
}

int main () {

    memset(h, -1, sizeof h);
    int n, m;
    cin >> n >> m >> s >> d;
    for (int i = 0; i < m; i ++) {
        int start, end, weight, cost;
        cin >> start >> end >> weight >> cost;
        add(start, end, weight), add(end, start, weight);
        cost_map[{start, end}] = cost, cost_map[{end, start}] = cost;
    }
    dijkstra();
    dfs(d, 0); 
    for (int i = ans.size() - 1; i >= 0; i --) cout << ans[i] << " ";
    cout << d << " ";
    cout << dist[d] << " " << min_cost;
    return 0;
}