HDU 2112 使用优先队列优化Dijkstra算法

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2112
使用优先队列优化的Dijkstra算法，其时间复杂度为 $O(ElogV)$。无论是稀疏图还是稠密图，优化后的运行速度都要比朴素Dijkstra快。
下面是几点需要了解的：

• 在Dijkstra算法中，dis[i]越小应该越先出队。在STL中我们可以使用greater<int>表示大于运算符，写成priority_queue<int> , vector<int>, greater<int> > Q这种形式来声明一个小整数优先出队的队列。
• 代码第12行的pair表示将dis数组的值与编号进行捆绑，以后作为一个整体放到优先队列中。（需要说明的是pair类型的排序规则是首先比较第一维，相等时再比较第二维）。因此代码中第24行的priority_queue < P, vector<P>, greater<P> > Q;就定义了一个由二元组构成的优先队列。

AC代码：

#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <algorithm> //fill函数的头文件
using namespace std;//HDU Accepted 2112 3151MS 2160K 1413 B G++
const int MAX_N = 10010;
const int INF = 0x3f3f3f3f;typedef pair<int, int> P;struct edge {int to, cost;edge(int tt, int tc) : to(tt), cost(tc){};
};
vector<edge> G[MAX_N];  //邻接表
map<string, int> mp;
int n, cost;int Dijkstra(int st, int ed) {int dis[MAX_N];fill(dis, dis+n+1, INF);//优先队列priority_queue < P, vector<P>, greater<P> > Q;dis[st] = 0;Q.push(P(0, st));while(!Q.empty()) {P p = Q.top();Q.pop();int v = p.second;  //获取pair p的第二维if(dis[v] < p.first)	continue;for(int i=0; i<G[v].size(); i++) {edge e = G[v][i];if(dis[e.to] > dis[v] + e.cost) {dis[e.to] = dis[v] + e.cost;Q.push(P(dis[e.to], e.to));}}}return dis[ed];
}int main() {string st, ed, s, e;while(~scanf("%d", &n) && n != -1) {mp.clear();for(int i=0; i<MAX_N; i++)	G[i].clear();int cnt = 1;cin>>st>>ed;mp[st] = cnt++;mp[ed] = cnt++;for (int i=0; i<n; i++) {cin>>s>>e>>cost;if(!mp[s])	mp[s] = cnt++;if(!mp[e])	mp[e] = cnt++;//双向G[mp[s]].push_back(edge(mp[e], cost));G[mp[e]].push_back(edge(mp[s], cost));  //本来应该是e，结果开始的时候没注意打成了s，导致一直WA... }int res = Dijkstra(mp[st], mp[ed]);if(res == INF)printf("-1\n");elseprintf("%d\n", res);}return 0;
}