暂时不理解为何在判断第二标尺时，要从后往前遍历
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 501;
const int inf = 1000000000;
int G[maxn][maxn], d[maxn], cost[maxn][maxn], n, m, st, ed, mincost = inf;
bool vis[maxn] = {false};
vector<int> pre[maxn], ans, temp;
void dijkstra(int st){fill(d, d + maxn, inf);d[st] = 0;for(int i = 0; i < n; i++){int u = -1, min = inf;for(int j = 0; j < n; j++){if(vis[j] == false && d[j] < min){min = d[j]; u = j;}}if(u == -1) return;vis[u] = true;for(int v = 0; v < n; v++){if(vis[v] == false && G[u][v] != inf){if(d[u] + G[u][v] < d[v]){d[v] = d[u] + G[u][v];pre[v].clear(); pre[v].push_back(u);}else if(d[u] + G[u][v] == d[v]){pre[v].push_back(u);}}}}
}
void dfs(int v){if(v == st){temp.push_back(v);int cos = 0;for(int i = temp.size() - 1; i > 0; i--){int now = temp[i], next = temp[i - 1];cos += cost[now][next];}if(cos < mincost){mincost = cos;ans = temp;}temp.pop_back(); return;}temp.push_back(v);for(int i = 0; i < pre[v].size(); i++){dfs(pre[v][i]);}temp.pop_back();
}
int main(){cin >> n >> m >> st >> ed;fill(G[0], G[0] + maxn * maxn, inf);fill(cost[0], cost[0] + maxn * maxn, inf);for(int i = 0; i < m; i++){int c1, c2, dis, cos;cin >> c1 >> c2 >> dis >> cos;G[c1][c2] = G[c2][c1] = dis;cost[c1][c2] = cost[c2][c1] = cos;}dijkstra(st); dfs(ed);for(int i = ans.size() - 1; i >= 0; i--) printf("%d ", ans[i]);printf("%d %d", d[ed], mincost);
}