[USACO08OPEN] Clear And Present Danger S

GitHub跳转原题关系图返回列表

Floyd 预处理岛屿两两最短危险值，再累加指定访问序列相邻项。

OJ: luogu

题目 ID: P2910

难度:普及

标签:Floyd最短路python

日期: 2026-07-17 03:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

必须按给定顺序经过岛屿，求允许经过其他岛屿时的最小总危险值。

思路

n<=100，用 Floyd 得到任意两岛最短路。序列相邻要求之间彼此独立，答案就是所有 dist[A_i][A_{i+1}] 之和。

Python 知识

  • 一次 read().split() 配合整数迭代器读取矩阵。
  • 缓存 row、through 减少三重循环索引开销。
  • zip(required, required[1:]) 枚举相邻序列元素。

代码

python
import sys


data = iter(map(int, sys.stdin.buffer.read().split()))
n, required_count = next(data), next(data)
required = [next(data) for _ in range(required_count)]
distance = [[next(data) for _ in range(n)] for __ in range(n)]
for middle in range(n):
    through = distance[middle]
    for start in range(n):
        row = distance[start]
        start_to_middle = row[middle]
        for end in range(n):
            row[end] = min(row[end], start_to_middle + through[end])
print(sum(distance[x - 1][y - 1] for x, y in zip(required, required[1:])))

原有 C++ 版本仍保留：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-17 01:40
 * update_at: 2026-07-17 01:40
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

复杂度

时间 O(n^3+M)，空间 O(n^2)。

总结

访问顺序固定时，先把每一段替换为两点最短路即可独立求和。