题解 | #最短路径问题#

#include<iostream>
using namespace std;
#define MAXdist 1<<29  //无穷大，代表无法到达
#define MAX 1001
int graph[MAX][MAX][2];//[][][0]len, [][][1]prize
int path[MAX][MAX];
int n, m;
int dist = 0, cost = 0;
void get_dist_and_cost(int s,int t) {//根据path和graph获得s to t的最短路径与费用
	if (path[s][t] == -1) {
		dist += graph[s][t][0];
		cost += graph[s][t][1];
	}
	else {
		int mid = path[s][t];//中间城市
		get_dist_and_cost(s, mid);
		get_dist_and_cost(mid, t);
	}
}
int main() {
	
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			graph[i][j][0] = graph[i][j][1] = MAXdist;
			path[i][j] = -1;
		}
	for (int i = 1; i <= m; i++) {
		int a, b, d, p;
		cin >> a >> b >> d >> p;
		if (d<graph[a][b][0] ||(d== graph[a][b][0]&&p< graph[a][b][1])) {
			graph[a][b][0] = d; graph[a][b][1] = p;
			graph[b][a][0] = d; graph[b][a][1] = p;
		}
	}
	int s, t;
	cin >> s >> t;
	//floyed算法
	for (int v = 1; v <= n; v++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j || i == v || j == v)continue;
				if (graph[i][j][0] > graph[i][v][0] + graph[v][j][0]) {
					graph[i][j][0] = graph[i][v][0] + graph[v][j][0];
					graph[i][j][1] = graph[i][v][1] + graph[v][j][1];
					path[i][j] = v;
				}
				if (graph[i][j][0] == graph[i][v][0] + graph[v][j][0]&&
					graph[i][j][1] > graph[i][v][1] + graph[v][j][1]) {
					graph[i][j][0] = graph[i][v][0] + graph[v][j][0];
					graph[i][j][1] = graph[i][v][1] + graph[v][j][1];
					path[i][j] = v;
				}	
			}
		}
	}
	get_dist_and_cost(s,t);
	cout << dist << " " << cost << endl;

	return 0;
}