机器人王国里的路径长度

题目描述

在一个机器人王国里，围绕首都分N层构建卫星城市。以首都为圆心，以路相连分出两个卫星城在第一个层，然后每个卫星城又有路相连分出两个卫星城在下一层，但每条路的长度不同。第N层的卫星城不再分出新的卫星城。现在人类只探知到所有直接相连的城市间的路程，你能计算某个卫星城到达首都的路程吗？

输入

第一行为N，表示机器人王国里有N层卫星城，N最大为10。从第二行开始，共$2^{N+1}-2$行，每行分别是城市的代号到其分出的卫星城的代号和它们间的路程。 代号用若干个字母表示，直连路程最大为100。最后一行是某卫星城的代号。

输出

根据最后一行的卫星城代号，求该卫星城到首都的路程。

样例输入

2
A F 20
B D 100
G A 5
G B 10
A C 6
B E 30
D

样例输出

110

题解

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

struct City {
    string parent;
    int distance;
};

int main() {
    int N;
    cin >> N;
    int num_cities = (1 << (N + 1)) - 2;
    unordered_map<string, City> cities;

    for (int i = 0; i < num_cities; i++) {
        string from, to;
        int distance;
        cin >> from >> to >> distance;
        cities[to] = {from, distance};
    }

    string target;
    cin >> target;

    int total_distance = 0;
    //反向追踪它的父键值，并累加它们的距离值，直到找不到目标键值为止
    while (cities.find(target) != cities.end()) {
        total_distance += cities[target].distance;
        target = cities[target].parent;
    }

    cout << total_distance << endl;

    return 0;
}