题解 | #最短路径问题#

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

using namespace std;

const int maxn = 1001;
const int maxm = 100000;

struct Edge {
	Edge(int a, int b, int d, int p):_a(a),_b(b),_d(d),_p(p){}

	int _a;
	int _b;
	int _d;
	int _p;
};

vector<Edge> graph[maxm];

struct PQueueNode {
	PQueueNode(int pos,int distance, int cost)
	:_pos(pos),_distance(distance),_cost(cost) {}

	int _pos;
	int _distance;
	int _cost;
};

bool operator<(const PQueueNode& lhs, const PQueueNode& rhs) {
	if (lhs._distance > rhs._distance) {
		return true;
	}
	else if (lhs._distance == rhs._distance && lhs._cost > rhs._cost) {
		return true;
	}
	else {
		return false;
	}
}

pair<int, int> Dijkstra(int source, int destination) {
	priority_queue<PQueueNode> pqueue;
	bool isVisited[maxn];
	int distance[maxn];
	int cost[maxn];

	for (int i = 0;i < maxn;i++) {
		isVisited[i] = false;
		distance[i] = -1;
		cost[i] = -1;
	}
	distance[source] = 0;
	cost[source] = 0;
	pqueue.push(PQueueNode(source, 0, 0));

	while (!pqueue.empty()) {
		int posMin = pqueue.top()._pos;
		pqueue.pop();

		if (isVisited[posMin] == true) {
			continue;
		}
		isVisited[posMin] = true;
		for (int i = 0;i < graph[posMin].size();++i) {
			int to = graph[posMin][i]._b;
			int to_weight = graph[posMin][i]._d;
			int to_cost = graph[posMin][i]._p;

			if (distance[to] == -1 ||
				distance[to] > distance[posMin] + to_weight ||
				(distance[to] == distance[posMin] + to_weight && cost[to] > cost[posMin] + to_cost) ||
				(distance[to] == distance[posMin] + to_weight && cost[to] == -1) ){
				distance[to] = distance[posMin] + to_weight;
				cost[to] = cost[posMin] + to_cost;
				pqueue.push(PQueueNode(to, distance[to],cost[to]));
			}
		}
	}
	return pair<int, int>{ distance[destination],cost[destination]};
}

int main() {
	int n, m;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			break;
		}
		for (int i = 0;i < m;i++) {
			graph[i].clear();
		}

		for (int i = 0;i < m;i++) {
			int a, b, d, p;
			cin >> a >> b >> d >> p;
			graph[a].push_back(Edge(a, b, d, p));
			graph[b].push_back(Edge(b, a, d, p));
		}

		int source, destination;
		cin >> source >> destination;
		cout << Dijkstra(source, destination).first << " " << Dijkstra(source, destination).second << endl;
	}
	return 0;
}