题意迷之简短。大意就是：一个城市i到另一个城市j的权值是|i-j|，同时，对于每个城市i存在一条捷径花费1权值从i到a[i]。求从第一城市开始到所有其余城市的最小权值。
还能说什么？bfs就好。
#coding gbk
#!usr/bin/env
n = int(input())
a = [0] + [n for i in range(n)]
e = [[i + 1, i - 1] if i < n else [i - 1] for i in range(0, n + 1)]
e[0] = []
a[1] = 0
for i, x in enumerate(map(int, input().split())):
if i + 1 != x: e[i + 1] += [x]
q = [(0, 1)]
while q:
l, cur = q.pop(0)
for x in e[cur]:
if l + 1 < a[x]:
a[x] = l + 1
q.append((l + 1, x))
print(*a[1:])
评论