#55257: cpp_answer


yp11451202@yphs.tp.edu.tw (705-38黃鈺潤)


#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    int dist;
    int speed;
    double time;
};

struct Node {
    int id;
    long long dist;
    double time;
    // 用於優先隊列的排序
    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

struct TimeNode {
    int id;
    double time;
    long long dist;
    bool operator>(const TimeNode& other) const {
        if (time != other.time) return time > other.time;
        return dist > other.dist; // 時間相同時,距離不影響但可作為基準
    }
};

void solve() {
    int N, M, A, B;
    cin >> N >> M >> A >> B;

    vector<vector<Edge>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v, d, s;
        cin >> u >> v >> d >> s;
        double t = (double)d / s;
        adj[u].push_back({v, d, s, t});
        adj[v].push_back({u, d, s, t});
    }

    // 第一次 Dijkstra: 找最短距離 X
    vector<long long> minDist(N + 1, INF);
    priority_queue<Node, vector<Node>, greater<Node>> pqDist;
    minDist[A] = 0;
    pqDist.push({A, 0, 0});

    while (!pqDist.empty()) {
        Node curr = pqDist.top(); pqDist.pop();
        if (curr.dist > minDist[curr.id]) continue;
        for (auto& edge : adj[curr.id]) {
            if (minDist[curr.id] + edge.dist < minDist[edge.to]) {
                minDist[edge.to] = minDist[curr.id] + edge.dist;
                pqDist.push({edge.to, minDist[edge.to], 0});
            }
        }
    }

    // 第二次 Dijkstra: 找最短時間對應的距離 Y
    vector<double> minTime(N + 1, 1e18);
    vector<long long> distOfMinTime(N + 1, INF);
    priority_queue<TimeNode, vector<TimeNode>, greater<TimeNode>> pqTime;
    
    minTime[A] = 0;
    distOfMinTime[A] = 0;
    pqTime.push({A, 0, 0});

    while (!pqTime.empty()) {
        TimeNode curr = pqTime.top(); pqTime.pop();
        if (curr.time > minTime[curr.id]) continue;
        for (auto& edge : adj[curr.id]) {
            if (minTime[curr.id] + edge.time < minTime[edge.to]) {
                minTime[edge.to] = minTime[curr.id] + edge.time;
                distOfMinTime[edge.to] = distOfMinTime[curr.id] + edge.dist;
                pqTime.push({edge.to, minTime[edge.to], distOfMinTime[edge.to]});
            }
        }
    }

    cout << minDist[B] << " " << distOfMinTime[B] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}