题解 P4779 【【模板】单源最短路径（标准版）】
GKxx
2018-08-14 16:30:04
### 本题解已更新 2018.11.18
是时候来一篇**线段树**的题解了。
线段树的效率还是挺优秀的，至少我自己测下来比我原来写的优先队列快。
先考虑一下如果要优化dijkstra算法，优先队列需要哪些操作，让线段树来实现它们。
- 查询队列是否为空，即还有没有要用来松弛其它点的点。
- 取出dist值最小的元素，并删除
- 修改一个点的dist值
如果我们用线段树来维护dist数组，那么修改操作就是非常简单的单点修改。我们只要用线段树来维护区间dist最小元素是谁(minpos，简称mp)即可。
但是线段树是不支持删除元素的，我们可以把dist[0]设置为恒为inf，如果要删除一个元素只要让它对应的叶节点mp值=0即可。这样的话就会保证查询dist最小元素的时候一定不会查到它；如果查到它就说明“优先队列”已经空了。
这是普通线段树的版本
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define dwn(I, A, B) for (int I = (A); I >= (B); --I)
#define erp(I, X) for (int I = head[X]; I; I = next[I])
template <typename T> inline void read(T& t) {
int f = 0, c = getchar(); t = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
if (f) t = -t;
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
read(t); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
template <typename T> inline bool chkMin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkMax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
const int maxn = 1e5 + 207, maxm = 2e5 + 207, inf = INT_MAX;
int v[maxm], w[maxm], head[maxn], next[maxm], tot;
int dist[maxn], mp[maxn << 2];
int n, m, s;
inline void ae(int x, int y, int z) {
v[++tot] = y; w[tot] = z; next[tot] = head[x]; head[x] = tot;
}
inline int cmp(int a, int b) { return dist[a] < dist[b] ? a : b; }
inline void upd(int x) { mp[x] = cmp(mp[x << 1], mp[x << 1 | 1]); }
void modify(int o, int l, int r, int pos, int val) {
if (l == r) { mp[o] = val; return; }
int mid = (l + r) >> 1;
if (pos <= mid) modify(o << 1, l, mid, pos, val);
else modify(o << 1 | 1, mid + 1, r, pos, val);
upd(o);
}
inline void dijkstra(int s) {
rep(i, 0, n) dist[i] = inf;
dist[s] = 0; modify(1, 1, n, s, s);
rep(t, 1, n - 1) {
int x = mp[1]; modify(1, 1, n, x, 0);
// 注意chkMin函数中已对dist[v[i]]赋值。
erp(i, x) if (chkMin(dist[v[i]], dist[x] + w[i]))
modify(1, 1, n, v[i], v[i]);
}
}
int main() {
read(n, m, s);
rep(i, 1, m) {
int x, y, z; read(x, y, z); ae(x, y, z);
}
dijkstra(s);
rep(i, 1, n) write(dist[i]), putchar(' ');
puts("");
return 0;
}
```
下面是zkw线段树的版本，比普通线段树快。（长达30行的程序头已略去）
参考了@Kelin大佬的写法，在这里表示感谢和膜拜。
```cpp
const int maxn = 1e5 + 207, maxm = 2e5 + 207, inf = INT_MAX;
int v[maxm], w[maxm], head[maxn], next[maxm], tot;
int dist[maxn], mp[maxn << 2], M = 1;
int n, m, s;
inline void ae(int x, int y, int z) { v[++tot] = y; w[tot] = z; next[tot] = head[x]; head[x] = tot; }
inline int cmp(int a, int b) { return dist[a] < dist[b] ? a : b; }
inline void build(int n) {
while (M < n + 2) M <<= 1;
mp[0] = n + 1;
}
inline void modify(int x, int nv) {
for (int i = x + M; dist[mp[i]] > nv; i >>= 1)
mp[i] = x;
dist[x] = nv;
}
inline void del(int x) {
for (mp[x += M] = 0, x >>= 1; x; x >>= 1)
mp[x] = cmp(mp[x << 1], mp[x << 1 | 1]);
}
inline void dijkstra(int s) {
rep(i, 0, n) dist[i] = inf;
build(n); modify(s, 0);
rep(t, 1, n - 1) {
int x = mp[1]; del(x);
// 这里没有对dist[v[i]]赋值，赋值操作在modify函数里进行，与上一个代码有所区别
erp(i, x) if (dist[v[i]] > dist[x] + w[i])
modify(v[i], dist[x] + w[i]);
}
}
int main() {
read(n, m, s);
rep(i, 1, m) {
int x, y, z; read(x, y, z); ae(x, y, z);
}
dijkstra(s);
rep(i, 1, n) write(dist[i]), putchar(' ');
puts("");
return 0;
}
```
另附强势压行版本。~~4行线段树你没有看错~~
```cpp
const int maxn = 1e5 + 207, maxm = 2e5 + 207, inf = INT_MAX;
int v[maxm], w[maxm], head[maxn], next[maxm], tot;
int dist[maxn], mp[maxn << 2], M = 1;
int n, m, s;
inline void ae(int x, int y, int z) { v[++tot] = y; w[tot] = z; next[tot] = head[x]; head[x] = tot; }
inline int cmp(int a, int b) { return dist[a] < dist[b] ? a : b; }
inline void build(int n) { while (M < n + 2) M <<= 1; mp[0] = n + 1; }
inline void modify(int x, int nv) { for (int i = x + M; dist[mp[i]] > nv; i >>= 1) mp[i] = x; dist[x] = nv; }
inline void del(int x) { for (mp[x += M] = 0, x >>= 1; x; mp[x] = cmp(mp[x << 1], mp[x << 1 | 1]), x >>= 1); }
inline void dijkstra(int s) {
rep(i, 0, n) dist[i] = inf;
build(n); modify(s, 0);
rep(t, 1, n - 1) {
int x = mp[1]; del(x);
erp(i, x) if (dist[v[i]] > dist[x] + w[i])
modify(v[i], dist[x] + w[i]);
}
}
int main() {
read(n, m, s);
rep(i, 1, m) {
int x, y, z; read(x, y, z); ae(x, y, z);
}
dijkstra(s);
rep(i, 1, n) write(dist[i]), putchar(' ');
puts("");
return 0;
}
```
~~线段树大法好~~