Computing the Minimum Cost of a Flight

求无负权有向图的单源最短路

May 17, 2017

题目链接：pdf

题目给出一个有向图，边的权值非负，求起点到终点的最短路。

用Dijkstra，基本思想是这样的：如果一个有向图权值非负，那么两点之间的最短路有最优子结构的性质。两点之间的最短路上的任意两点之间的路径也是最优的。

设S -> ... -> u -> ... -> v -> ... -> t是从S到t的一条最短路，那么这条路径上从u到v的部分也是u到v的最短路。反证：假设从u到v存在一条更短的路径L，那么用L替换S到t中从u到v的部分，就可以得到一条从S到v的更短的路径，由于我们假设原来的路径是从S对v的最短路，得出矛盾。

这样，设d(S, t)是S -> ... -> u -> t是S到t的最短路。则：

d(S, t) = d(S, u) + w(u, t)

所以我们可以不断地对所有边的进行松弛操作，直到没有边可以松弛。这个时候就可以得到单源最短路。这样的循环最多进行V次，每次最多进行E次松弛操作，因此复杂度是V*E。

显然我们不必每次都对所有边进行松弛。我们可以记录下以后不需要松弛的点，也就是最短路已经确定的点，所以我们可以把所有点分成两个集合，一个集合表示这些点到源点的最短路已经确定，另一个集合表示最短路还不确定。

也就是说每次松弛的循环中，我们可以把松弛过的点放到一个优先队列中，然后从中选择到源点距离最小的出队，它就是最短距离已经确定的点。继续从这个开始松弛操作，一直循环到队列为空。每个点入队一次，出队一次。总共循环V次，每次循环中要出队最小元素（VlogV），对这个点相连的所有边进行松弛并且入队(ElogV)。总共是(E+V)logV。

// Mon May 15 10:45:45 CST 2017
// Mon May 15 11:29:58 CST 2017

/*
最简单的Dijkstra
 */

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;
typedef pair<int, int> PII;

class Comp {
public:
  bool operator() (const PII &a, const PII &b) {
    return a.first > b.first;
  }
};

int distance(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, int t) {
  vector<int> visited(adj.size(), false);
  priority_queue<PII, vector<PII>, Comp > que;
  vector<int> dist(adj.size(), INT_MAX);

  visited[s] = true;
  dist[s] = 0;
  que.push(make_pair(dist[s], s));

  while (!que.empty()) {
    int top = que.top().second;
    que.pop();

    for (size_t i = 0; i < adj[top].size(); ++i) {
      int tmp = dist[top] + cost[top][i];

      if (dist[adj[top][i]] > tmp) {
	dist[adj[top][i]] = tmp;
	que.push(make_pair(tmp, adj[top][i]));
      }
    }

  }

  return (dist[t] == INT_MAX ? -1 : dist[t]);
}

int main() {
  int n, m;
  while(std::cin >> n >> m) {
    vector<vector<int> > adj(n, vector<int>());
    vector<vector<int> > cost(n, vector<int>());
    for (int i = 0; i < m; i++) {
      int x, y, w;
      std::cin >> x >> y >> w;
      adj[x - 1].push_back(y - 1);
      cost[x - 1].push_back(w);
    }
    int s, t;
    std::cin >> s >> t;
    s--, t--;
    std::cout << distance(adj, cost, s, t) << "\n";
  }
}

Read more