题解 | #最短路径问题#

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int dist[N]; // 每个点到s的距离 
int value[N];
int g[N][N];
int w[N][N]; // 花费 
bool st[N];
int n, m;
void dijkstra(int s, int t){
	memset(dist, 0x3f, sizeof(dist));
	memset(value, 0x3f, sizeof(value));
	dist[s] = 0;
	value[s] = 0;
	
	for (int i=1; i<=n; i++){
		int tmp = -1;
		for (int j=1; j<=n; j++){
			if (!st[j] && (tmp == -1 || dist[j] <= dist[tmp])){
				if (tmp == -1 || value[j] < value[tmp]){
					tmp = j;
				}
			}
		}
		st[tmp] = true;
		
		for (int j=1; j<=n; j++){
			if (dist[j] > dist[tmp] + g[tmp][j]){
				dist[j] = dist[tmp] + g[tmp][j];
				value[j] = value[tmp] + w[tmp][j];
			}
            else if (dist[j] == dist[tmp] + g[tmp][j]){
                if (value[j] > value[tmp] + w[tmp][j]){
                    value[j] = value[tmp] + w[tmp][j];
                }
            }
		} 
	}
}

int main(){
	
	while (cin >> n >> m){
		if (n == 0 && m == 0){
			break;
		}
		memset(g, 0x3f, sizeof(g));
		memset(w, 0x3f, sizeof(w));
		for (int i=1; i<=m; i++){
			int x, y, d, p;
			cin >> x >> y >> d >> p;
			if (g[x][y] > d){
                g[x][y] = d;
                g[y][x] = d;
                w[x][y] = p;
                w[y][x] = p;
            }
            else if (g[x][y] == d && w[x][y] > p){
                g[x][y] = d;
                g[y][x] = d;
                w[x][y] = p;
                w[y][x] = p;
            
            }
		}
		int s, t;
		cin >> s >> t;
		dijkstra(s, t);
//		for (int i=1; i<=n; i++){
//			cout << dist[i] << " ";
//		}
		cout << dist[t] << " " << value[t] << endl;
				
	}
	return 0;
}