http://wikioi.com/problem/1079/

gohome_dijkstra_algoritthm.cc

#define pp pair<int, char>

int main() {
    int m, weight;
    cin >> m; 
    int ans = INT_MAX;
    char ansc;
    map<char, int> distance;
    map<char, map<char, int> > graph;
    for (int i = 0; i < m; ++i) {
        char from, to;
        cin >> from >> to >> weight;
        graph[to][from] = min(graph[to][from] ? graph[to][from] : INT_MAX, weight);
        graph[from][to] = min(graph[from][to] ? graph[from][to] : INT_MAX, weight);
    }
    priority_queue<pp, vector<pp>, greater<pp> > q;
    distance['Z'] = 0;
    q.push(pp(0, 'Z'));
    while (!q.empty()) {
        pp t = q.top();
        q.pop();
        for (map<char, int>::iterator it = graph[t.second].begin();
                it != graph[t.second].end(); ++it) {
            if (!distance.count(it->first) || 
                    distance[t.second] + it->second < distance[it->first]) {
                distance[it->first] = distance[t.second] + it->second;
                q.push(pp(distance[it->first], it->first));
                if(ans > distance[it->first] && it->first >= 'A' && it->first < 'Z') {
                    ans = distance[it->first];
                    ansc = it->first;
                } 
            }
        }
    }
    cout << ansc << " " << ans << endl;
}

我抽象出了一个通用 dijkstra() 方法，代码在此 https://gist.github.com/soulmachine/6751059