[PAT解题报告] All Roads Lead to Rome
又是最短路，dijkstra算法的变种。
（1） 记录最短路条数， 更新的时候：
用k更新i的时候，有两种情况
如果最短路长度相等，num[i] += num[k]
如果最短路更短 num[i] = num[k]
（2） happiness 和 bypass 这两个没的说，如果要更新的话
happiness[i] = b[i] + happiness[k]
bypass[i] = bypass[k] + 1
所以只是在更新上做手脚，别忘记记录pre[i] = k，以方便倒着还原出路径来。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;
const int inf = 1000000000;
const int N = 202;
map<string,int> id;
int cost[N],happy[N],bypass[N],num[N],pre[N],n,a[N][N],b[N];
bool mark[N];
string name[N];
char s[10];
void dijkstra(int s) {
for (int i = 0; i < n; ++i) {
cost[i] = bypass[i] = inf;
num[i] = happy[i] = 0;
mark[i] = false;
}
num[s] = 1;
cost[s] = bypass[s] = 0;
pre[s] = -1;
for (int j = 0; j < n; ++j) {
int k = -1;
for (int i = 0; i < n; ++i) {
if ((!mark[i]) && ((k < 0) || (cost[i] < cost[k]))) {
k = i;
}
}
mark[k] = true;
for (int i = 0; i < n; ++i) {
if ((!mark[i]) && (a[k][i] < inf)) {
int temp = cost[k] + a[k][i];
if (temp < cost[i]) {
cost[i] = temp;
happy[i] = happy[k] + b[i];
bypass[i] = bypass[k] + 1;
num[i] = num[k];
pre[i] = k;
}
else if (temp == cost[i]) {
num[i] += num[k];
int mayhappy = happy[k] + b[i];
int maybypass = bypass[k] + 1;
if ((mayhappy > happy[i]) || ((mayhappy == happy[i]) && (maybypass < bypass[i]))) {
happy[i] = mayhappy;
bypass[i] = maybypass;
pre[i] = k;
}
}
}
}
}
}
void print(int x) {
if (x) {
print(pre[x]);
printf("->");
}
printf("%s",name[x].c_str());
}
int main() {
int m;
scanf("%d%d%s",&n,&m,s);
id[name[0] = s] = 0;
b[0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = inf;
}
}
for (int i = 1; i < n; ++i) {
scanf("%s%d",s,&b[i]);
id[name[i] = s] = i;
}
for (;m;--m) {
scanf("%s",s);
int x = id[s];
scanf("%s",s);
int y = id[s];
int z;
scanf("%d",&z);
a[x][y] = a[y][x] = min(a[x][y],z);
}
dijkstra(0);
int x = id["ROM"];
printf("%d %d %d %d\n",num[x],cost[x],happy[x],happy[x] / bypass[x]);
print(x);
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1087
