题解 | #最短路径问题#

#include <bits/stdc++.h>

using namespace std;
const int INF = INT_MAX;
#define  MAXN  1000 + 10

//存储边结点
struct Edge {
    int a;
    int b;
    int length;
    int prise;

    Edge(int _u, int _v, int _length, int _prise) {
        a = _u;
        b = _v;
        length = _length;
        prise = _prise;
    }
};

//存储待访问的结点队列的元素
struct PQueueNode {
    int nextVex;//下一个结点的编号。
    int distance;//目前到达下个结点的距离
    PQueueNode(int _nextVex, int _distance) {
        nextVex = _nextVex;
        distance = _distance;
    }
};

//给相邻结点排序，放入大根堆
bool operator<(PQueueNode lhs, PQueueNode rhs) {
    // 自定义一个 < 运算符，表示后面的元素全部都小于堆顶元素
    // 运算符重载
    // 重载 < 原本的小于号 有两个参数 返回值是bool
    // 自定义一个函数 参数数量不变，返回值类型不变，名字是operator 运算符
    // 若a<b 返回true 大根堆
    // 若a<b 返回false 小根堆
    if (lhs.distance < rhs.distance) {
        return false;
    } else {
        return true;
    }
}

vector<Edge> graph[MAXN];//指的是vector<Edge> graph有300个。最多有300个顶点
int eachCost[MAXN];//到每个节点的代价
int dst[MAXN];//存储到每个节点的距离

void Dijkstra(int s, int t) {
    priority_queue<PQueueNode> p_que;
    dst[s] = 0;//初始到起点的距离是零
    eachCost[s] = 0;//初始到起点的代价是零
    PQueueNode qnode(s, 0);
    p_que.push(qnode);//入队
    while (!p_que.empty()) {
        //BFS算法。更新当前结点相邻的结点。
        int a = p_que.top().nextVex;//当前节点
        p_que.pop();
        for (int i = 0; i < graph[a].size(); ++i) {//访问结点u所有的相邻结点。。。
            int b = graph[a][i].b;
            int length = graph[a][i].length;//a到b的距离
            int cost = graph[a][i].prise;
            if ((dst[b] == dst[a] + length && eachCost[b] > eachCost[a] + cost) ||
                dst[b] > dst[a] + length) {//距离为正无穷或者小于上一个节点加上权重。
                dst[b] = dst[a] + length;//更新。
                eachCost[b] = eachCost[a] + cost;
                PQueueNode next(b, dst[b]);
                p_que.push(next);
            }
        }
    }
    printf("%d %d\n", dst[t], eachCost[t]);
}

int main() {
    int n;
    int m;
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0 && m == 0) {
            return 0;
        }

        memset(graph, 0, sizeof(graph));//初始化
        fill(dst, dst + n + 1, INF);
        fill(eachCost, eachCost + n + 1, INF);
        for (int i = 0; i < m; ++i) {
            int u;
            int v;
            int length;
            int cost;
            scanf("%d%d%d%d", &u, &v, &length, &cost);
            Edge e1(u, v, length, cost);
            graph[u].push_back(e1);
            Edge e2(v, u, length, cost);
            graph[v].push_back(e2);
        }
        int s;
        int t;
        scanf("%d%d", &s, &t);
        Dijkstra(s, t);
        
    }
    return 0;
}