HDOJ2680——Dijkstra堆优化

参考博客
使用邻接矩阵实现的dijkstra算法的复杂度是O(V²)。使用邻接表的话，更新最短距离只需要访问每条边一次即可，因此这部分的复杂度是O(E).但是每次要枚举所有的顶点来查找下一个使用的顶点，因此最终复杂度还是O(V²)。在|E|比较小时，大部分的时间都花在了查找下一个使用的顶点上，因此需要使用合适的数据结构进行优化。

需要优化的是数值的插入(更新)和取出最小值两个操作，因此使用堆就可以了。把每个顶点当前的最短距离用堆来维护，在更新最短距离时，把对应的元素往根的方向移动以满足堆的性质。而每次从堆中取出的最小值就是下一次要用的顶点。这样堆中的元素共有O(V)个，更新和取出的操作有O(E)次，因此整个算法的复杂度是O(ElogV)。
下面是使用STL的priority_queue实现。在每次更新时往堆里插入当前最短距离和顶点的值对。插入的次数是O(E)次，当取出的最小值不是最短距离的话，就丢弃这个值。这样整个算法也可以在同样的时间内完成。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int,int> P;   //用pair存储优先队列中的数据。first中是当前最短距离，second中是定点名称
const int inf = 0x3f3f3f3f;
const int N = 1024;
vector<P> mat[N];
int n,m,d[N];

void dijkstra()
{
  priority_queue<P,vector<P>,greater<P> > pq;  //定义规则为越小越优先出的队列
  for(int i=0;i<=n;i++) d[i] = inf;
  d[0] = 0;
  pq.push(make_pair(0,0));  //把起点压入队列
  while(!pq.empty())
  {
    P p = pq.top(); //将队列顶部元素弹出
    pq.pop();
    int node = p.second;
    int len = mat[node].size();
    if(d[node] < p.first) continue;  //已经有更短的路径与他连接，那么忽略。
    for(int i=0;i<len;i++)
    {
      int tmp = mat[node][i].first;
      if(d[tmp] > d[node] + mat[node][i].second)
      {
        d[tmp] = d[node] + mat[node][i].second;
        pq.push(make_pair(d[tmp],tmp));
      }
    }
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int s,a,b,cost,tmp;
  while(cin >> n >> m >> s)
  {
    for(int i=0;i<=n;i++) mat[i].clear();   //初始化邻接表
    for(int i=1;i<=m;i++)
    {
      cin >> a >> b >> cost;
      mat[a].push_back(make_pair(b,cost));
    }
    cin >> tmp;
    for(int i=1;i<=tmp;i++)
    {
      cin >> a;
      mat[0].push_back(make_pair(a,0));
    }
    dijkstra();
    cout << ((d[s] == inf) ? -1 : d[s]) << endl;
  }
  return 0;
}