阿里巴巴2017实习生招聘在线编程测验--基础平台研发工程师

Find.cpp

#include <iostream>
#include <unordered_map>
#include <queue>
#include <sstream>

/*
 * 阿里巴巴2017实习生招聘在线编程测验--基础平台研发工程师
 * 思路：使用邻接矩阵表示图， 因为地理位置不超过100，所以可以先建立起一个 100x100 的矩阵
 * 然后读入数据，依次建立矩阵（使用两个哈希表建立起地理位置和下标的对应关系）
 * 建立完成后，使用 Dijkstra 算法算出最短路径，注意使用一个数组保存
 */
/*
 * Dijkstra 算法伪代码：
 * void Dijkstra(Vertex s){
 *    while(1){
 *       v = 未收录顶点中dist最小者
 *       if(这样的v不存在）
 *            break;
 *       collected[V] = true; // visited
 *       for (V 的每个邻接点 w){
 *         if (collected[W]==false&&dist[V]+E[V,W]<dist[W]){
 *              dist[W] = dist[V] + E[V][W];
 *              path[W] = V;
 *         }
 *       }
 *    }
 * }
 */
using namespace std;
#define MAX_VERTEX 100
#define INF INT32_MAX

string
buildGraph(vector<vector<long>> &graph, unordered_map<string, int> &str2idx, unordered_map<int, string> &idx2str) {
    int N;
    cin >> N;
    string s, d, line, t;
    int idx = -1;
    for (int i = 0; i < N; i++) {
        cin >> line;
        istringstream lineStream(line);
        getline(lineStream, s, ',');
        getline(lineStream, d, ',');
        getline(lineStream, t, ',');
        int s_idx = -1, d_idx = -1;
        if (str2idx.find(s) != str2idx.end()) {//存在对应 index
            s_idx = str2idx[s];
        } else {
            idx++;
            s_idx = idx;
            str2idx[s] = s_idx;//记录 str 到 idx 关系
            idx2str[s_idx] = s;//记录 idx 到 str 关系
        }
        if (str2idx.find(d) != str2idx.end()) {
            d_idx = str2idx[d];
        } else {
            idx++;
            d_idx = idx;
            str2idx[d] = d_idx;
            idx2str[d_idx] = d;
        }
        graph[s_idx][d_idx] = stoi(t);
    }
    string start;
    cin >> start;
    return start;
}

struct node {
    int id;
    long weight;//用 struct 记录权重和对应结点对应关系
    //用 pair 实现也可以
};

struct cmp {
    bool operator()(const node &a, const node &b) {
        return a.weight > b.weight;
    }

};

string Find() {
    vector<vector<long>> graph;
    unordered_map<int, string> idx2str;
    unordered_map<string, int> str2idx;
    for (int i = 0; i < MAX_VERTEX; i++) {
        vector<long> row(MAX_VERTEX, INF);
        graph.push_back(row);
    }

    string start = buildGraph(graph, str2idx, idx2str);

    priority_queue<node, vector<node>, cmp> q;
    vector<int> last_parent(MAX_VERTEX, -1);
    vector<bool> isVisited(MAX_VERTEX, false);
    vector<node> shortest_path;

    for (int i = 0; i < MAX_VERTEX; i++) {
        node d;
        d.id = i;
        d.weight = INF;
        shortest_path.push_back(d);
    }

    int start_idx = str2idx[start];
    shortest_path[start_idx].weight = 0;
    q.push(shortest_path[start_idx]);

    while (!q.empty()) {
        node top = q.top();
        q.pop();

        int u = top.id;
        if (isVisited[u])
            continue;
        isVisited[u] = true;
        for (int i = 0; i < MAX_VERTEX; i++) {
            if (i != u && !isVisited[i] && shortest_path[i].weight > shortest_path[u].weight + graph[u][i]) {
                shortest_path[i].weight = shortest_path[u].weight + graph[u][i];
                last_parent[i] = u;
                q.push(shortest_path[i]);
            }
        }
    }

    int parent_idx = last_parent[str2idx["XH"]];
    string res = "XH";
    while (parent_idx != -1) {
        res = idx2str[parent_idx] + "->" + res;
        parent_idx = last_parent[parent_idx];
    }
    return  res;

}

int main() {

    /*
     * test case 1
     1
     AA,XH,1
     AA
     */

    /*
     * test case 2
     4
     AA,BB,20
     AA,CC,30
     BB,XH,50
     CC,XH,10
     AA
     */

    /*
     * test case 3
     10
     AA,BB,10
     AA,CC,5
     BB,DD,1
     BB,CC,2
     CC,BB,3
     CC,XH,2,
     CC,DD,9,
     DD,XH,4
     XH,AA,7
     XH,DD,6
     AA
     */

    /*
     * test case 4
     8
     AA,BB,1
     BB,CC,2,
     CC,DD,3
     DD,EE,4
     EE,FF,5
     FF,GG,6
     GG,HH,7
     HH,XH,8
     AA
     */


    string s = Find();
    cout << s;

}