Dijkstra

# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

const int INF = 0xffffff;
struct ArcNode{
    int v;
    int distance, cost; // 记录两种边权，cost为第二标尺
};

// 顶点编号从0 - N-1
int N, M; // 顶点数、边数
int S, D; // 起点、终点

vector<ArcNode> G[510];
int dist[510]; // 最短路径长度
int cost[510]; // 最少路径花费
bool vis[510];
vector<int> pre(510); // 打印路径

void Dijkstra(int s){
    fill(dist, end(dist), INF);
    fill(cost, end(cost), INF);
    fill(vis, end(vis), false);
    for(int i = 0;i < N;++i) pre[i] = i;
    dist[s] = 0;
    cost[s] = 0;

    for(int i = 0; i < N ;++i){
        int u = -1;
        int MIN = INF;
        for(int j = 0; j < N ;++j){
            if(vis[j] == false && dist[j] < MIN){
                u = j;
                MIN = dist[j];
            }
        }
        if(u == -1) return;
        vis[u] = true;
        for(ArcNode next: G[u]){
            if(vis[next.v] == false){
                if(dist[u] + next.distance  < dist[next.v]){
                    dist[next.v] = dist[u] + next.distance;
                    cost[next.v] = cost[u] + next.cost;
                    pre [next.v] = u; 
                } 
                else
                if(dist[u] + next.distance == dist[next.v]){
                    // 不要为了偷懒写min函数了
                    if(cost[u] + next.cost < cost[next.v]){
                        cost[next.v] = cost[u] + next.cost;
                        pre [next.v] = u; // 第二标尺更小的时候最优路径也要更新，用min函数就没更新，会错。
                    }
                }
            }
        }
    }
}

void printPATH(int v){
    if(v == S){
        cout << S << " ";
        return;
    }

    printPATH(pre[v]);
    cout << v << " ";

}

int main(){
    cin >> N >> M >> S >> D;
    for(int i = 0;i < M;++i){
        int C1, C2, d, c;
        cin >> C1 >> C2 >> d >> c;
        G[C1].push_back({C2, d, c});
        G[C2].push_back({C1, d, c});
    }
    Dijkstra(S);
    printPATH(D);
    cout << dist[D] << " " << cost[D] << endl;

    return 0;
}