[PAT解题报告] All Roads Lead to Rome

#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;
}