Flight ticket list - Airbnb

airbnb面试题汇总

http://www.1point3acres.com/bbs/thread-210100-1-1.html

給一個flight tickets的list，其中flight ticket包括出發地，到達地，價錢，現在規定最多k個connections，找出從A到B花費最少的path和cost。
.鏈枃鍘熷垱鑷�1point3acres璁哄潧
我是直接BFS做

问下BFS的话怎么保存路径呢

for numConnections = 1 to k, keep shortest path from city A to any other city

每一项包括departure, arrival, cost，然后给一个整数k, 表示最多允许k次中转。给定起始地点A，到达地点B, 要求输出从A到B的最小花费，最多k次中转。BFS一层一层扫。

def min_cost(flights, start, end, k):
    info = collections.defaultdict(set)
    for tour, cost in flights:
        st, ed = tour.split("->")
        info[st].add((ed, cost))

    cur_level = {start: 0}
    ans = 0x7FFFFFF
    for _ in xrange(k + 1):
        next_level = {}
        for port, cur_cost in cur_level.iteritems():
            for nx, cost in info[port]:
                if nx == end:
                    ans = min(ans, cost + cur_cost)
                else:
                    if nx not in next_level:
                        next_level[nx] = cost + cur_cost
                    else:
                        next_level[nx] = min(next_level[nx], cost + cur_cost)
        cur_level = next_level
    return ans

///C++: 太丑
typedef pair<string, int> costInfo;
int minCostFlight(const vector<string>& flights, string start, string end, int k) {
    unordered_map<string, set<costInfo> > costMap;
    unordered_map<string, int> reached[2];
    int ans = INT_MAX;
    for (auto flight : flights) 
        auto nx = flight.find("->", 0);
        auto comma = flight.find(',', nx + 2);
        string st = flight.substr(0, nx);
        string ed = flight.substr(nx + 2, comma - nx - 2);
        int cost = atoi(flight.substr(comma + 1).c_str());
        costMap[st].insert(make_pair(ed, cost));
    }
    reached[0][start] = 0;
    for (int i = 0, j = 0; i <= k; ++i) {
        int nxIdx = (j + 1) % 2;
        reached[nxIdx].clear();
        for (auto st : reached[j]) {
            for(auto ed : costMap[st.first]) {
                if (ed.first == end) {
                    ans = min(ans, ed.second + st.second);
                } else {
                    if (!reached[nxIdx].count(ed.first))
                        reached[nxIdx][ed.first] = ed.second + st.second;
                    else
                        reached[nxIdx][ed.first] = min(reached[nxIdx][ed.first], ed.second + st.second);
                }
            }
        }
        j = nxIdx;
    }
    return ans;
}