水题解的一天。
题目大意
给定 \(n\) 个点 任意两点 \(i,j\) 间有权值为 \(|i-j|\) 的双向边,另有 \(n\) 条权值为 \(1\) 的单向边,求以 \(1\) 为起点的单源最短路径。
\(1\leqslant n\leqslant200000\)
解题思路
由于 \(n\) 太大了,\(n^2\) 条边不能接受。
考虑简化, 发现 \(i \to \ k\) 之间的边可以由 \(\forall i \leq j<k,j \to j+1\) 这些权值为 \(1\) 的边拼成。
然后跑 dij
最短路即可
总时间复杂度是 \(\mathcal{O}(n\log n)\)。
CODE
#include <bits/stdc++.h>
using namespace std;
const int _ = 200005;
int tot, head[_], to[_ * 3], nxt[_ * 3], w[_ * 3];
int vis[_], dis[_];
void add(int x, int y, int z)
{
to[++tot] = y;
w[tot] = z;
nxt[tot] = head[x];
head[x] = tot;
}
void dij()
{
priority_queue<pair<int, int>> q;
memset(dis, 0x3f, sizeof dis);
q.push(make_pair(0, 1));
dis[1] = 0;
while (!q.empty())
{
int x = q.top().second;
q.pop();
if (vis[x])
continue;
vis[x] = 1;
for (int i = head[x]; i; i = nxt[i])
{
int y = to[i], z = w[i];
if (dis[y] > dis[x] + z)
{
dis[y] = dis[x] + z;
q.push(make_pair(-dis[y], y));
}
}
}
}
int n;
signed main()
{
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
add(i, i + 1, 1);
add(i + 1, i, 1);
}
for (int i = 1; i <= n; i++)
{
int x;
scanf("%d", &x);
add(i, x, 1);
}
dij();
for (int i = 1; i <= n; i++)
printf("%d ", dis[i]);
return 0;
}