题解 | #KY152 最短路径问题#

Dijstra算法 + 堆优化

void Dijkstra(int s)
{
	vector<int> dist;        //该数组存储从源点s到w的最短距离, dist[s] = 0;
	vector<int> path;        //该数组储存从源点s到w的路径上经过的点, s-->w path[w] = s
	vector<bool> collected;  //该数组表示当前结点是否已经收录于最短路径集合中了

	for (int i = 0; i < vertexNum; i++)
	{
		dist.push_back(65535);
		path.push_back(-1);
		collected.push_back(false);
	}

	dist[s] = 0;
	for (auto w : Adj(s))
	{
		dist[w] = ptrGraph[s][w];
	}

	while (1)
	{
		int v = 65535;

		for (int j = 0; j < vertexNum; j++)
		{
			if (!collected[j] && dist[j] < 65535)
			{
				v = j;
			}
		}

		if (v == 65535)
		{
			break;
		}

		collected[v] = true;

		for (auto w : Adj(v)) 
		{
			if (collected[w] == false)
			{
				if (dist[v] + ptrGraph[v][w] < dist[w])
				{
					dist[w] = dist[v] + ptrGraph[v][w];
					path[w] = v;
				}
			}
		}
	}
}

该算法的时间复杂度，如果是直接扫描所有未收录的顶点，判断其dist的最小的顶点，则为 O(V^2 + E)。while循环为V次，每次扫描一遍顶点也需要V次，for循环对v的每个邻接点w的处理，总共相当于遍历了一遍图中的所有的边E。

若是将dist的值存于最小堆，则获取未收录顶点中dist值最小者为O(logV)，在更新dist值的时候也需要O(logV)的时间复杂度。总的时间复杂度为O(VlogV + ElogV)，当为稀疏图时，近似于O(VlogV)。如果对于E不是V^2的数量级，而是V的数量级，这种方式效果要好一些。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int to;
    int length;
    int price;
    Edge(int b, int l, int p) : to(b), length(l), price(p) { }
};

struct Point {
    int index;    //该点的编号
    int distance;     //该点距离源点的距离
    Point(int _id, int _dst) : index(_id), distance(_dst) { }
    friend bool operator < (const Point& p1, const Point& p2) {
        return p1.distance > p2.distance;
    }
};

pair<int, int> Dijstra(vector<vector<Edge>>& Adj, int s, int t) {
    int n = Adj.size();
    vector<int> dist(n, INT32_MAX);
    vector<int> cost(n);    
    vector<bool> collected(n, false);
    priority_queue<Point> pq;
    dist[s] = 0;
    cost[s] = 0;
    pq.push(Point(s, dist[s]));
    
    while (!pq.empty()) {
        int u = pq.top().index;
        pq.pop();
        if (collected[u]) continue;
        collected[u] = true;
        for (int i = 0; i < Adj[u].size(); i++) {
            int v = Adj[u][i].to;
            int len = Adj[u][i].length;
            int p = Adj[u][i].price;
            if (!collected[v]) {
                if ((dist[v] > dist[u] + len) || 
                    (dist[v] == dist[u] + len && cost[v] > cost[u] + p)) {
                    dist[v] = dist[u] + len; 
                    cost[v] = cost[u] + p;
                    pq.push(Point(v, dist[v]));
                }
            }
        }
    }
    return pair<int, int>(dist[t], cost[t]);
}

int main() 
{
    int N, M;
    while (cin >> N >> M) {
        if (N == 0 && M == 0) break;
        vector<vector<Edge>> Adj(N+1);
        int a, b, l, p;
        while (M--) {
            cin >> a >> b >> l >> p;
            Adj[a].push_back(Edge(b, l, p));
            Adj[b].push_back(Edge(a, l, p));
        }
        int S, F;
        cin >> S >> F;
        pair<int, int> res = Dijstra(Adj, S, F);
        cout << res.first << " " << res.second << endl;
    }
    return 0;
}