CF20C Dijkstra? 题解

Content

给定一张 \(n\) 个点 \(m\) 条边的无向图，请判断是否有一条可行的从 \(1\) 到 \(n\) 的路径，有的话输出长度最短的，没有的话输出 -1。

数据范围：\(2\leqslant n\leqslant 10^5\)，\(0\leqslant m\leqslant 10^5\)，每条边的长度不超过 \(10^6\)。

Solution

这道题的标题当中看上去是在误导你不用 \(\textsf{Dijkstra}\)，其实已经给出了这道题目的做法就是：\(\textsf{Dijkstra}\)。为了优化复杂度，我用了堆优化 + \(\textsf{Dijkstra}\)。

那么 \(\textsf{Dijkstra}\) 如何做到能够输出路径呢？这里我们就需要用到一个 \(\textit{pre}\) 数组，其中 \(\textit{pre}_i\) 表示最短路径中在 \(i\) 点前面的点。我们可以在 \(\textsf{Dijkstra}\) 处理 \(\textit{dis}\) 数组的时候就把这个 \(pre\) 更新一遍，就像这样：

for(int i = h[x]; i; i = e[i].nxt) {

	int y = e[i].to, z = e[i].v;

	if(dis[y] > dis[x] + z) { //更新最短路

		dis[y] = dis[x] + z, pre[y] = x; //更新最短路的长度和当前点在最短路上的前一个节点。

		q.push(make_pair(-dis[y], y));

	}

}

那么我们又如何判断是否存在从 \(1\) 到 \(n\) 最短路径呢？这里给出两种方法：

第一种，还记得我们在跑 \(\textsf{Dijkstra}\) 的时候要先做什么吗？没错，初始化 \(\textit{dis}\) 数组。由于是最短路，我们需要将这个 \(\textit{dis}\) 数组的初值设得尽可能大，又因为在数据范围中我们发现：

\(0\leqslant m\leqslant 10^5\)，每条边的长度不超过 \(10^6\)。

所以我们就知道了，可能最长的最短路长度为 \(10^5\times 10^6=10^{11}\)，因此我们需要开 long long，并将这个 \(\textit{dis}\) 数组赋初值赋在 \(10^{11}\) 以上，下面这一段以笔者在代码中赋的初值 \(10^{18}\) 为准。

然后我们就可以通过这个来判断是否存在到 \(n\) 的最短路径了：只需要判断是否有 \(\textit{dis}_n\neq10^{18}\) 即可，因为如果 \(\textit{dis}_n=10^{18}\)，那么就说明 \(\textit{dis}_n\) 还从来没有更新过，自然也就不存在从 \(1\) 到 \(n\) 的最短路径了。

第二种，就要用到这一题中所引入的 \(\textit{pre}\) 数组了，我们可以从 \(n\) 开始，直接利用 \(x\leftarrow\textit{pre}_x\) 向前推最短路径上的节点，看是否能够推到 \(1\)，如果最终不能够推到 \(1\) 就说明不存在从 \(1\) 到 \(n\) 的最短路径。

两种方法虽然看上去第一种的表述要多一些，但实际上这两种方法的实现程度都是不难的，因此推荐大家把两种写法都写一遍。

另外，我们也可以从这道题目中吸取一些教训：标题并不一定就决定了你的做题思路，你的做题思路应当从题面中通过思考而得出。

Code 1

const int N = 1e5 + 7, M = N << 1;

int n, m, u, v, w, cnt, fl, vis[N], h[M], ans[N], pre[N];

ll dis[N];

struct edge {int v, to, nxt;}e[M];

pq<pair<ll, int> > q;

iv a_e(int u, int v, int w) {e[++cnt] = (edge){w, v, h[u]}; h[u] = cnt;}

iv dj() {

	F(i, 1, 100000) dis[i] = 1e18;

	dis[1] = 0, q.push(mp(0, 1));

	while(!q.empty()) {

		int x = q.top().se; q.pop();

		if(vis[x]) continue; vis[x] = 1;

		E {

			int y = e[i].to, z = e[i].v;

			if(dis[y] > dis[x] + z) {

				dis[y] = dis[x] + z, pre[y] = x;

				q.push(mp(-dis[y], y));

			}

		}

	}

}

int main() {

	n = Rint, m = Rint;

	F(i, 1, m) {

		u = Rint, v = Rint, w = Rint;

		a_e(u, v, w), a_e(v, u, w);

	}

	dj();

	for(int cur = n; cur; cur = pre[cur]) ans[++ans[0]] = cur;

	if(dis[n] != (ll)1e18) R(i, ans[0], 1) write(ans[i]), putchar(" \n"[i == n]);

	else puts("-1");

    return 0;

}

Code 2

const int N = 1e5 + 7, M = N << 1;

int n, m, u, v, w, cnt, fl, vis[N], h[M], ans[N], pre[N];

ll dis[N];

struct edge {int v, to, nxt;}e[M];

pq<pair<ll, int> > q;

iv a_e(int u, int v, int w) {e[++cnt] = (edge){w, v, h[u]}; h[u] = cnt;}

iv dj() {

	F(i, 1, 100000) dis[i] = 1e18;

	dis[1] = 0, q.push(mp(0, 1));

	while(!q.empty()) {

		int x = q.top().se; q.pop();

		if(vis[x]) continue; vis[x] = 1;

		E {

			int y = e[i].to, z = e[i].v;

			if(dis[y] > dis[x] + z) {

				dis[y] = dis[x] + z, pre[y] = x;

				q.push(mp(-dis[y], y));

			}

		}

	}

}

int main() {

	n = Rint, m = Rint;

	F(i, 1, m) {

		u = Rint, v = Rint, w = Rint;

		a_e(u, v, w), a_e(v, u, w);

	}

	dj();

	for(int cur = n; cur; cur = pre[cur]) {

		ans[++ans[0]] = cur;

		if(cur == 1) fl = 1;

	}

	if(fl) R(i, ans[0], 1) write(ans[i]), putchar(" \n"[i == n]);

	else puts("-1");

    return 0;

}

巴特西

CF20C Dijkstra? 题解

Content

Solution

Code 1

Code 2

最新文章

热门文章