PAT甲级A1087---最短路径

1087 All Roads Lead to Rome (30分)

分析：

dijkstra+dfs

C++：

#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

const int maxn = 210;
const int INF = 1 << 30;
int G[maxn][maxn];
int weight[maxn];
bool isVisit[maxn];
int d[maxn];
vector<int> pre[maxn];
vector<int> tempPath, path;
int n, k;
string start;
map<string, int> mp1;//城市名->编号
map<int, string> mp2;//编号->城市名
int num = 0;
int maxWeight = -1;
double maxAvg = -1;

void dijkstra(int s) {
    fill(d, d + maxn, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, min = INF;
        for (int j = 0; j < n; j++) {
            if (isVisit[j] == false && d[j] < min) {
                min = d[j];
                u = j;
            }
        }
        if (u == -1) {
            return;
        }
        isVisit[u] = true;
        for (int j = 0; j < n; j++) {
            if (isVisit[j] == false && d[u] + G[u][j] < d[j]) {
                d[j] = d[u] + G[u][j];
                pre[j].clear();
                pre[j].push_back(u);
            } else if (isVisit[j] == false && d[u] + G[u][j] == d[j]) {
                pre[j].push_back(u);
            }
        }
    }
}

void dfs(int index) {
    tempPath.push_back(index);
    if (index == 0) {
        num++;
        int value = 0;
        for (int i = tempPath.size() - 2; i >= 0; i--) {
            int id = tempPath[i];
            value += weight[id];
        }
        double avg = 1.0 * value / (tempPath.size() - 1);
        if (value > maxWeight) {
            maxWeight = value;
            maxAvg = avg;
            path = tempPath;
        } else if (maxWeight == value && avg > maxAvg) {
            maxAvg = avg;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    for (int i = 0; i < pre[index].size(); i++) {
        dfs(pre[index][i]);
    }
    tempPath.pop_back();
}

int main() {
    cin >> n >> k >> start;
    mp1[start] = 0;
    mp2[0] = start;
    string city;
    for (int i = 1; i < n; i++) {
        cin >> city >> weight[i];
        mp1[city] = i;
        mp2[i] = city;
    }
    fill(G[0], G[0] + maxn * maxn, INF);
    string a, b;
    int value;
    for (int i = 0; i < k; i++) {
        cin >> a >> b >> value;
        int a1 = mp1[a], b1 = mp1[b];
        G[a1][b1] = G[b1][a1] = value;
    }
    dijkstra(0);
    int index = mp1["ROM"];
    dfs(index);
    printf("%d %d %d %d\n", num, d[index], maxWeight, (int) maxAvg);
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << mp2[path[i]];
        if (i != 0) {
            cout << "->";
        }
    }
    return 0;
}