- #include<iostream>
- #include<algorithm>
- #define MAX 1002
- #define INF (1<<20)
- using namespace std;
- struct COST{ int d, p; };
- int n, m;
- COST cost[MAX][MAX];
- COST d[MAX];
- bool used[MAX];
- void dijkstra(int s){
- for (int i = 0; i < MAX; i++){
- d[i].p = INF;
- d[i].d = INF;
- }
- fill(used, used + MAX, false);
- d[s].d = 0; d[s].p = 0;
- while (true){
- int v = -1;
- for (int i = 0; i < n; i++){
- if (!used[i] && (v == -1 || d[i].d < d[v].d )){ v = i; }
- }
- if (v == -1)break;
- used[v] = true;
- for (int i = 0; i < n; i++){
- if ((d[i].d > (d[v].d + cost[v][i].d)) ){
- d[i].d = d[v].d + cost[v][i].d;
- d[i].p = d[v].p + cost[v][i].p;
- }
- else if (d[i].d ==(d[v].d + cost[v][i].d)){
- if (d[i].p > d[v].p + cost[v][i].p){
- d[i].p = d[v].p + cost[v][i].p;
- }
- }
- }
- }
- }
- int main()
- {
- int s, t, a, b, c, p;
- while (true){
- cin >> n >> m;
- if (n + m == 0)break;
- for (int i = 0; i < n; i++){
- for (int j = 0; j < n; j++){
- cost[i][j].d = INF;
- cost[i][j].p = INF;
- }
- }
- for (int i = 0; i < m; i++){
- cin >> a >> b >> c >> p;
- if (c < cost[a-1][b-1].d){
- cost[a - 1][b - 1].d = c;
- cost[a - 1][b - 1].p = p;
- cost[b - 1][a - 1] = cost[a - 1][b - 1];
- }
- }
- cin >> s >> t;
- dijkstra(s - 1);
- cout << d[t - 1].d <<" "<< d[t - 1].p << endl;
- }
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1411201410979.html
来源: http://www.codesnippet.cn/detail/1411201410979.html