题解 | #最短路径问题#

#include <cstring>
#include <climits>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1002;
struct Edge {
    int to;  //终点
    int length; //长度
    int weight; //权重
    Edge(int t, int l, int w): to(t), length(l), weight(w) {}
};
vector<Edge> graph[N];
struct Point {
    int number;
    int distance;
    Point(int n, int d): number(n), distance(d) {}
    bool operator<(const Point& p)const {
        return distance > p.distance;
    }
};
int dis[N]; //记录原点到每个顶点的最短距离
int cost[N]; //花费
void Dijkstra(int s) {
    priority_queue<Point> pq;
    dis[s] = 0;
    cost[s] = 0;
    pq.push(Point(s, dis[s]));
    while (!pq.empty()) {
        int u = pq.top().number;
        pq.pop();
        for (int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i].to;
            int d = graph[u][i].length;
            int w = graph[u][i].weight;
            if ((dis[v] > dis[u] + d) || (dis[v] == dis[u] + d && cost[v] > cost[u] + w)) {
                dis[v] = dis[u] + d;
                cost[v] = cost[u] + w;
                pq.push(Point(v, dis[v]));
            }
        }
    }
    return;
}
int main() {
    int n, m, d, p;
    int s, t;
    while (cin >> n >> m) {
        if (n == 0 && m == 0) break;
        memset(graph, 0, sizeof(graph));
	    //这里编号为从1~n，故fill(dis,dis+n+1,INT_MAX);
        fill(dis, dis + n + 1, INT_MAX);
        fill(cost, cost + n + 1, INT_MAX);
        for (int i = 0; i < m; i++) {
            int from, to, len, weight;
            cin >> from >> to >> len >> weight;
            graph[from].push_back(Edge(to, len, weight));
            graph[to].push_back(Edge(from, len, weight));
        }
        cin >> s >> t;
        Dijkstra(s);
        cout << dis[t] << " " << cost[t] << endl;
    }
    return 0;
}