[PAT解题报告] Travel Plan

给定一个无向图，每条边有一个长度，还有一个费用，要求从起点到终点，先总路程长度最小，如果最短路长度相同，再让费用最小——保证这时答案是唯一的。

分析：还是dijkstra算法，这个算法之前考过很多次了。例如1013， 1018。我们有两个指标优化，首先是距离，更新距离的时候顺便可以更新费用。只有确定更新距离的时候，再考虑费用，距离相同的话，费用取最小的。

还有注意多重边的处理(题目可能没有多重边), 取距离(长度)最短的，如果长度相同，取费用最小的。

dijkstra算法可以在更新时记录很多东西，总结一下包括：

（1）最短路的长度——这个显然

（2）长度相同的时候，可以让第二关键词达到最优（最大或者最小），本题第二关键词是费用

（3）具体的最短路径，我们只需要在更新距离的时候，记录pre[x] = y表示到当前节点x的上一个节点是y，最后从终点递归倒回起点就能求出具体路径。另外如果不喜欢递归，可以从终点倒过来算最短路，就算到起点，然后从终点沿着pre的信息(或许叫next更好些）一步一步正着走下去，也可以求出最短路径来。

代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int inf = 1000000000;
const int N = 502;

int n;
bool mark[N];    
int a[N][N];
int b[N][N];
int dis[N];
int cost[N];
int pre[N];

void print(int now,int from) {
    if (now != from) {
        print(pre[now], from);
    }
    printf("%d ",now);
}

void dijkstra(int from) {
    for (int i = 0; i < n; ++i) {
        cost[i] = dis[i] =  inf;
        mark[i] = false;
    } 
    cost[from] = dis[from] = 0;
    for (int j = 0; j < n; ++j) {
        int k = -1;
        for (int i = 0; i < n; ++i) {
            if ((!mark[i]) && ((k < 0) || (dis[i] < dis[k]))) {
                k = i;
            }
        }
        mark[k] = true;
        for (int i = 0; i < n; ++i) {
            if ((!mark[i]) && (a[k][i] < inf)) {
                int maydis = dis[k] + a[k][i];
                int maycost = cost[k] + b[k][i];
                if ((maydis < dis[i]) || ((maydis == dis[i]) && (maycost < cost[i]))) {
                    pre[i] = k;
                    dis[i] = maydis;
                    cost[i] = maycost;
                }
            }
        } 
        
    }
}



int main() {
int m, from, to;
    scanf("%d%d%d%d",&n,&m,&from,&to);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            a[i][j] = b[i][j] = inf;
        }
    }
    for (;m;--m) {
        int x,y,d,c;
        scanf("%d%d%d%d",&x,&y,&d,&c);
        if ((a[x][y] > d) || ((a[x][y] == d) && (b[x][y] > c))) {
            a[x][y] = a[y][x] = d;
            b[x][y] = b[y][x] = c;
        }
    }
    dijkstra(from);
    print(to,from);
    printf("%d %d\n",dis[to],cost[to]);
    return 0;
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1030