HDU1874（最短路+dijkstra+堆优化）

解题报告：同 $O (n^{2})$ 算法类似，不过用邻接表存图在松弛的时候优化了遍历不相邻点的复杂度，在查询当前最短径的时候直接用小根堆弹出，复杂度从 $O (n)$ 降到 $O (l o g E)$ 。

Code：

#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>

using namespace std;
const int maxn = (int)1e5+5;
const int inf = 0x3f3f3f3f;

struct Node{
	int to;
	int w;
	Node(int to, int w) {
		this->to = to;
		this->w = w;
	}
	
	bool operator < (const Node& A) const {
		return w > A.w;
	}
};
int n, m, start, k;
vector<Node> tab[maxn];
bool vis[maxn];
int dist[maxn]; //distance

void init(int n, int m) {
	for (int i = 0; i < n; i++) {
		tab[i].clear();
	}
	
	int v,u,w;
	for (int i = 0; i < m; i++) {
		scanf("%d%d%d",&u,&v,&w);
		tab[u].push_back(Node(v, w));
		tab[v].push_back(Node(u, w));
	}
}

priority_queue<Node> pq;
void dijkstra(int from) {  //dijkstra + 堆优化 
	fill(dist, dist+n, inf);
	memset(vis, false, sizeof(vis));
	while (!pq.empty()) {
		pq.pop();
	}
	dist[from] = 0;
	pq.push(Node(from, 0));
	while (!pq.empty()) {
		Node x = pq.top();
		pq.pop();
		int to = x.to;
		if (vis[to]) continue;
		vis[to] = true;
		for (int i = 0; i < tab[to].size(); i++) {
			int u = tab[to][i].to;
			int w = tab[to][i].w;
			if (!vis[u] && dist[u] > dist[to] + w) {
				dist[u] = dist[to] + w;
				pq.push(Node(u, dist[u]));
			}
		}
	}
}

int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		init(n, m);
		scanf("%d%d", &start, &k);
		dijkstra(start);
		printf("%d\n", dist[k] == inf ? -1 : dist[k]);
	}
	return 0;
}