[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
投递美的集团等公司10个岗位 >
