稀疏图

Dijkstra求最短路 II

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n号点，则输出 ?1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 ?1。

数据范围

1≤n,m≤1.5×10⁵
图中涉及边长均不小于 0，且不超过 10000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m;
//邻接表
int h[N], w[N], e[N], ne[N], idx;
//距离
int dist[N];
// 每个点的最短路是否已经确定
bool st[N];

void add(int a, int b, int c) {
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}


int dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;

	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({ 0, 1 });

	while (heap.size()) {
		auto t = heap.top();
		heap.pop();

		int ver = t.second, distance = t.first;
		if (st[ver]) {
			continue;
		}

		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (dist[j] > distance + w[i]) {
				dist[j] = distance + w[i];
				heap.push({ dist[j], j });
}
		}
	}

	if (dist[n] == 0x3f3f3f) {
		return -1;
	}
	return dist[n];

}

int main() {
	//scanf("%d%d", &n, &m);
	cin >> n >> m;
	memset(h, -1, sizeof h);


	while (m--) {
		int a, b, c;
		//scanf("%d%d%d", &a, &b, &c);
		cin >> a >> b >> c;
		add(a, b, c);
	}

	int t = dijkstra();

	//printf("%d\n", t);
	cout << t << endl;
	return 0;
}

堆优化版的Dijkstra