4074. 铁路与公路
摘要
Title: 4074. 铁路与公路
Tag: floyd
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
4074. 铁路与公路
-
题意
略
-
思路
最大是400x400的完全图，也就是每两个点，不是铁路就是公路，而且边权为1
也就是说肯定有一条从1到n的路径，是直通的，边权为1
另一条就用Floyd来求即可，这样也保证了不会相遇 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41'''
Author: NEFU AB-IN
Date: 2023-03-19 15:17:56
FilePath: \Acwing\4074\4074.py
LastEditTime: 2023-03-19 15:32:18
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations
N = int(410)
INF = int(2e9)
g1 = [[INF] * N for _ in range(N)]
g2 = [[INF] * N for _ in range(N)]
def floyd(g):
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
return g[1][n]
n, m = read()
for i in range(m):
u, v = read()
g1[u][v] = g1[v][u] = 1
for i in range(1, n + 1):
for j in range(1, n + 1):
if i == j:
g1[i][j] = g2[i][j] = 0
if g1[i][j] == INF:
g2[i][j] = g2[j][i] = 1
ans = max(floyd(g1), floyd(g2))
print(-1 if ans == INF else ans)