题解 | #最短路径问题#

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int>PII;
const int N = 1010, M = 1e5 + 10, INF = 0x3f3f3f3f;
int n, m, a, b, d, p, s, t;
int dist[N], cost[N];
bool st[N];

struct Edge {
	int to, lenth, price;
	Edge(int b, int d, int p): to(b), lenth(d), price(p) {};
};

vector<Edge> g[M];

PII dijkstra(int s, int t) {
	memset(dist, 0x3f, sizeof dist);
	memset(cost, 0x3f, sizeof cost);
	memset(st, 0, sizeof st);
	dist[s] = 0, cost[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII> >heap;
	heap.push({0, s});
	while (!heap.empty()) {
		PII tmp = heap.top();// 取距离起点最近的点
		heap.pop();
		int elem = tmp.second, dis = tmp.first;
		if (st[elem]) continue;
		st[elem] = true;
		for (int i = 0; i < g[elem].size(); i++) { // 遍历所有邻接点
			int j = g[elem][i].to;
			int w = g[elem][i].lenth;
			int v = g[elem][i].price;
			if ((dist[j] > dis + w) || (dist[j] == dis + w && cost[j] > cost[elem] + v)) {
				dist[j] = dis + w;
				cost[j] = cost[elem] + v;
				heap.push({dist[j], j});
			}
		}
	}
	if (dist[t] == INF) return {INF, INF};
	else return {dist[t], cost[t]};
}

int main() {
	// freopen("input.txt", "r", stdin);
	while (scanf("%d%d", &n, &m) != EOF) {
		if (n == 0 && m == 0) break;
		memset(g, 0, sizeof g);
		for (int i = 0; i < m; i++) {
			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));
		}
		cin >> s >> t;
		PII res = dijkstra(s, t);
		cout << res.first << " " << res.second << '\n';
	}
	return 0;
}