Codeforces Round #361 (Div. 2)B. Mike and Shortcuts

题意迷之简短。大意就是:一个城市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:])

相关日志

  1. 2016.07.13

    安利一波答案 经典算法设计

      (更多…)

  2. 2016.05.09

    FZU 2091 播放器

    题目地址:http://acm.fzu.ed…

  3. 2016.06.18

    竞赛技巧:读取一行到string类

    string类中定义了getline函数; …

  4. 2016.05.04

    FZU 2041 checker(搜索)

    题目链接:http://acm.fzu.ed…

  5. 2016.05.11

    ZOJ 3704 I am Nexus Master!(模拟)

    题目链接:http://acm.zju.ed…

  6. 2016.05.09

    FZU 2093 寻找兔子(状压dp)

    题目地址:http://acm.fzu.ed…

评论

还没有评论。

在此评论中不能使用 HTML 标签。