摘要
Title: 4240. 青蛙
Tag: 最短路模型、spfa
Memory Limit: 64 MB
Time Limit: 3000 ms

4240. 青蛙

题意

求从1号点到2号点的所有路径中的单次最长距离的最小值
思路

求最长边的最小值
可以用spfa来做， $dist[i]$ 数组不再表示起点到 $i$ 的最小距离，而是表示起点到 $i$ 的所有边的最大值的最小值
当dist[v] > max(dist[u], w)时，就对 $dist[v]$ 进行松弛，也就是求最小值；而max操作相当于求这一路径的边的最大值

ps：当出现菊花图时，用邻接矩阵，肉眼可见的快

代码

'''
Author: NEFU AB-IN
Date: 2022-04-16 10:21:21
FilePath: \ACM\Acwing\4240.py
LastEditTime: 2022-04-16 10:22:45
'''
from collections import deque

N = 220
INF = int(1e9)
g = [[INF] * N for _ in range(N)]
dist, st = [INF] * N, [0] * N


def spfa(u):
    st[u] = 1
    q = deque()
    q.appendleft(u)
    dist[u] = 0
    while q:
        u = q.pop()
        st[u] = 0
        for v in range(1, n + 1):
            if dist[v] > max(dist[u], g[u][v]):
                dist[v] = max(dist[u], g[u][v])
                if st[v] == 0:
                    st[v] = 1
                    q.appendleft(v)
    return dist[2]


def cale(x1, y1, x2, y2):
    return pow((x1 - x2)**2 + (y1 - y2)**2, 0.5)

cnt = 0
while True:
    cnt += 1
    n = int(input())
    if n == 0:
        break
    lst = [0]
    dist, st = [INF] * N, [0] * N
    g = [[INF] * N for _ in range(N)]
    for i in range(n):
        x, y = map(int, input().split())
        lst.append([x, y])
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            x1, y1 = lst[i]
            x2, y2 = lst[j]
            w = cale(x1, y1, x2, y2)
            g[i][j] = w
            g[j][i] = w
    spfa(1)
    print(f"Scenario #{cnt}")
    print(f"Frog Distance = {spfa(1):.3f}")
    print()
    tmp = input()

4240. 青蛙

题意

思路

代码