wikioi 1079 回家, http://www.wikioi.com/problem/1079/

wikioi1079.cpp

// wikioi 1079 回家, http://www.wikioi.com/problem/1079/
#include <iostream>
#include <queue>
#include <map>
#include <utility>
#include <climits>

using namespace std;

/** 边的权值类型，可以为int, float, double. */
typedef int graph_weight_t;

/** 顶点的编号，可以为char, int, string等. */
typedef char graph_vertex_id_t;

/**
 * @struct 图，用邻接表.
 */
struct graph_t {
    size_t nv; // 顶点数
    size_t ne; // 边数
    // 邻接表，存放边的信息，如权重等
    map<graph_vertex_id_t, map<graph_vertex_id_t, graph_weight_t> > matrix;
};


/**
 * @brief Dijkstra算法求单源最短路径.
 * @param[in] g 图
 * @param[in] start 起点
 * @param[out] dist dist[v]存放的是起点到v的最短路径长度
 * @param[out] father father[v]存放的是最短路径上指向v的上一个顶点
 * @return 无
 */
void dijkstra(const graph_t &g, graph_vertex_id_t start,
        map<graph_vertex_id_t, graph_weight_t> &distance,
        map<graph_vertex_id_t, graph_vertex_id_t> &father) {
    /* 起点到顶点的最短距离. */
    typedef pair<graph_weight_t, graph_vertex_id_t> to_dist_t;

    // 小根堆
    priority_queue<to_dist_t, vector<to_dist_t>, greater<to_dist_t> > q;
    distance[start] = 0;  // 自己到自己，距离为0
    q.push(to_dist_t(0, start));
    while (!q.empty()) {
        const to_dist_t u = q.top(); q.pop();
        if (g.matrix.find(u.second) == g.matrix.end()) continue;

        for (map<graph_vertex_id_t, graph_weight_t>::const_iterator iter =
                g.matrix.at(u.second).begin();
                iter != g.matrix.at(u.second).end(); ++iter) {
            const graph_vertex_id_t v = iter->first;
            const graph_weight_t w = iter->second;

            if (!distance.count(v) || distance[u.second] + w < distance[v]) {
                distance[v] = distance[u.second] + w;
                father[v] = u.second;
                q.push(to_dist_t(distance[v], v));
            }
        }
    }
    return;
}

/**
 * @brief 打印从起点到终点的最短路径
 * @param[in] father Dijkstra计算好的father数组
 * @param[in] end 终点
 * @return 无
 */
void print_path(const map<graph_vertex_id_t, graph_vertex_id_t> &father,
        graph_vertex_id_t end) {
    if (!father.count(end)) {
        cout << end;
    } else {
        print_path(father, father.at(end));
        cout << "->" << end;
    }
}

/** 读取输入，构建图. */
void read_graph(graph_t &g) {
    cin >> g.ne;
    for (size_t i = 0; i < g.ne; ++i) {
        graph_vertex_id_t from, to;
        graph_weight_t weight;
        cin >> from >> to >> weight;
        // 输入数据可能存在重复，取其小者
        g.matrix[to][from] = min(g.matrix[to][from] ?
                g.matrix[to][from] : INT_MAX, weight);
        g.matrix[from][to] = g.matrix[to][from];
    }
}

int main() {
    graph_t g;
    map<graph_vertex_id_t, graph_weight_t> distance;
    map<graph_vertex_id_t, graph_vertex_id_t> father;

    read_graph(g);

    dijkstra(g, 'Z', distance, father);

    // 在大写字母中找最小
    graph_weight_t min_dist = INT_MAX;
    graph_vertex_id_t target; // 终点
    for (map<graph_vertex_id_t, graph_weight_t>::const_iterator iter =
            distance.begin(); iter != distance.end(); ++iter) {
        if (min_dist > iter->second && iter->first >='A' && iter->first < 'Z') {
            min_dist = iter->second;
            target = iter->first;
        }
    }
    cout << target << " " << min_dist << endl;
    return 0;
}