题解 | 最短路径问题

//常规dijkstra算法，先考虑最短路径排列，再建数组更新费用，更新费用时注意要在最短路径的前提下更新；
//关于数组规模的问题，目的地可能为n，目的地又可能作为容器指标，所以容器数量至少为n+1；
#include <cstdint>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
const int MAXN = 1000;
const int INF = INT16_MAX;
struct Edge {
    int to;
    int length;
    int price;
    Edge(int b, int d, int p): to(b), length(d), price(p) {}
};
struct Point {
    int number;
    int distance;
    int fee;
    Point(int num, int dis, int fee): number(num), distance(dis), fee(fee) {}
    bool operator<(const Point& p)const {
        if (distance != p.distance) {
            return distance > p.distance;
        } else {
            return fee > p.fee;
        }
    }
};
vector<Edge>G[MAXN];
int dis[MAXN];
int Fee[MAXN];
void dijkstra(int s) {
    priority_queue<Point>Q;
    dis[s] = 0;
    Fee[s] = 0;
    Q.push(Point(s, dis[s], Fee[s]));
    while (!Q.empty()) {
        int u = Q.top().number;
        Q.pop();
        for (int i = 0; i < G[u].size(); i++) {
            int d = G[u][i].length;//距离
            int v = G[u][i].to; //目的地
            int p = G[u][i].price; //价格
            if (dis[v] > dis[u] + d) {
                dis[v] = dis[u] + d;
                Fee[v] = Fee[u] + p;
                Q.push(Point(v, dis[v], Fee[v]));
            } else if (dis[v] == dis[u] + d) {
                if (Fee[v] > Fee[u] + p) {
                    Fee[v] = Fee[u] + p;
                    Q.push(Point(v, dis[v], Fee[v]));
                }
            }
        }
    }
    return ;
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        fill(dis, dis + n + 1, INF); //n+1
        fill(Fee, Fee + n + 1, INF); ///n+1
        memset(G, 0, sizeof(G));
        for (int i = 0; i < m; i++) {
            int a;
            int b;
            int d;
            int p;
            scanf("%d %d %d %d", &a, &b, &d, &p);
            G[a].push_back(Edge(b, d, p));
            G[b].push_back(Edge(a, d, p));
        }
        int u, v;
        scanf("%d %d", &u, &v);
        dijkstra(u);
        printf("%d %d\n", dis[v], Fee[v]);
    }
    return 0;
}