题解 | #最短路径问题#

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

using namespace std;

#define N 1010

struct Edge {
    int y;
    int weight;
    int spend;
};
struct Node {
    int x;//源点到该点的距离
    int dist;//路径长度
    int money;//到该节点花费
};

bool operator<(Node l, Node r) {
    if (l.dist == r.dist) {
        return l.money > r.money;
    }
    return l.dist > r.dist;
}

vector<Edge> v[N];

void Dijikstra(int s, int t, int n) {
    int Dist[N];
    int Money[N];
    bool isvisit[N];
    for (int i = 0; i < N; i++) {
        Dist[i] = INT32_MAX;
        Money[i] = INT32_MAX;
        isvisit[i] = false;
    }//初始化结束
    Dist[s] = 0;
    Money[s] = 0;
    priority_queue<Node> pqueue;
    Node node;
    node.x = s;
    node.dist = Dist[s];
    node.money = Money[s];
    pqueue.push(node);
    while ((pqueue.empty() == false)) {
        int cur = pqueue.top().x;
        pqueue.pop();
        if (isvisit[cur] == true) {
            continue;
        }
        isvisit[cur] = true;
        //找到他的邻居
        for (int i = 0; i < v[cur].size(); i++) {
            int x = v[cur][i].y;
            int weight = v[cur][i].weight;
            int spend = v[cur][i].spend;
            if (Dist[x] > Dist[cur] + weight) {
                Dist[x] = Dist[cur] + weight;
                Money[x] = Money[cur] + spend;
                Node node;
                node.money = Money[x];
                node.dist = Dist[x];  //更新源点到该点的距离
                node.x = x;
                pqueue.push(node);
            } else if (Dist[x] == Dist[cur] + weight) {
                if (Money[x] > Money[cur] + spend) {
                    Money[x] = Money[cur] + spend;
                    Node node;
                    node.money = Money[x];
                    node.dist = Dist[x];  //更新源点到该点的距离
                    node.x = x;
                    pqueue.push(node);
                }
            }
        }

    }
    printf("%d %d", Dist[t], Money[t]);
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        //更新边
        for (int i = 0; i < n; i++) {
            v[i].clear();
        }
        for (int i = 0; i < m; i++) {
            int s1, s2, s3, s4;
            scanf("%d%d%d%d", &s1, &s2, &s3, &s4);
            Edge e;
            e.y = s2;
            e.weight = s3;
            e.spend = s4;
            v[s1].push_back(e);
            e.y = s1;
            v[s2].push_back(e);
        }
        int s, t;
        scanf("%d%d", &s, &t);
        Dijikstra(s, t, n);
    }
    return 0;
}