2024蓝桥杯每日一题（最短路径）

备战2024年蓝桥杯 -- 每日一题
Python大学A组

        试题一：奶牛回家
        试题二：Dijkstra求最短路 II
        试题三：spfa求最短路
        试题四：作物杂交

---

试题一：奶牛回家

【题目描述】

        晚餐时间马上就到了，奶牛们还在各自的牧场中悠闲的散着步。当农夫约翰摇动铃铛，这些牛就要赶回牛棚去吃晚餐。在吃晚餐之前，所有奶牛都在自己的牧场之中，有些牧场中可能没有奶牛。每个牧场都通过一条条道路连接到一个或多个其他牧场（可能包括其自身）。有时，两个（可能是相同的）牧场通过一条以上的道路相连。至少存在一个牧场与牛棚通过一条道路直接相连。所有奶牛都能够成功的从自己的牧场沿道路返回牛棚。聪明的奶牛们总会选择最短的路径回到牛棚之中。每条道路都是可以双向行走的，奶牛的行走速度也都一样。我们用 a∼z 和 A∼Y 来标记所有的牧场。所有用大写字母标记的牧场中都存在一头奶牛，所有用小写字母标记的牧场中都不存在奶牛。牛棚的标记为 Z，这里最初是没有奶牛的。现在你需要确定，哪一头奶牛能够最快到达牛棚，输出它最初所在的牧场的标记，并输出它走过的路径的长度。注意，同一字母大小写标记的两个牧场（例如，牧场 A 和牧场 a）是两个完全不同的牧场。

【输入格式】

        第一行包含整数 P，表示连接牧场以及牛棚的道路的条数。

        接下来 P 行，每行包含两个字母以及一个整数，表示被一条道路连接的两个牧场的标记，以及这条道路的长度。

【输出格式】

        输出一个字母和一个整数，表示最快回到牛棚的牛最初所在的牧场的标记以及它走过的路径的长度。

        数据保证最快回到牛棚的牛只有一头。

【数据范围】

        1≤P≤10000
        所有道路长度均不超过 1000

【输入样例】

5
A d 6
B d 3
C e 9
d Z 8
e Z 3

【输出样例】

B 11

【解题思路】

        Dijkstra题，简单变形了

【Python程序代码】

n = int(input())
g = [[1e9]*(60) for _ in range(60)]
def dy(a):
    if 'a'<=a<='z':
        a = ord(a)-ord('a')+1
    else:
        a = ord(a)-ord('A')+27
    return a
 
 
for i in range(n):
    a,b,c = map(str,input().split())
    a = dy(a); b = dy(b)
    g[a][b]=g[b][a]=min(g[a][b],int(c))
dist = [1e9]*100
dist[52]=0
def dijkstra():
    st = [0]*(100)
    for i in range(51):
        t = -1
        for j in range(1,53):
            if not st[j] and (t==-1 or dist[t]>dist[j]):
                t = j
        st[t]=1
        for j in range(1,53):
            dist[j] = min(dist[j],dist[t]+g[t][j])
 
dijkstra()
res,idx = 1e9,27
for i in range(27,52):
    if dist[i]
        res = dist[i]
        idx = i
print(chr(ord('A') + idx -27) ,res)
    

---

试题二：Dijkstra求最短路2

【题目描述】

        给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

【输入格式】

        第一行包含整数 n 和 m。

        接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

【输出格式】

        输出一个整数，表示 1 号点到 n 号点的最短距离。

        如果路径不存在，则输出 −1。

【数据范围】

        1≤n,m≤1.5×105
        图中涉及边长均不小于 0，且不超过 10000

【输入样例】

3 3
1 2 2
2 3 1
1 3 4

【输出样例】

3

【解题思路】

        Dijkstra模板题

【Python程序代码】

from heapq import *
n,m = map(int,input().split())
h,e,ne,w,idx = [-1]*(n+10),[0]*(m+10),[0]*(m+10),[0]*(m+10),0
def add(a,b,c):
    global idx
    e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx; idx+=1
for i in range(m):
    a,b,c = map(int,input().split())
    add(a,b,c)
def dijkstra():
    dist = [1e9]*(n+10)
    st = [0]*(n+10)
    dist[1]=0
    q = []
    heappush(q,(0,1))
    while q:
        dis,idk = heappop(q)
        if st[idk]:continue
        st[idk]=1
        i = h[idk]
        while i!=-1:
            j = e[i]
            if dist[j]>w[i]+dis:
                dist[j] =dis+w[i]
                heappush(q,(dist[j],j))
            i = ne[i]
    if dist[n]==1e9:return -1
    return dist[n]
 
print(dijkstra())

---

试题三：spfa求最短路

【题目描述】

        给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

        请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

【输入格式】

        第一行包含整数 n和 m。

        接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。

【输出格式】

        输出一个整数，表示 1 号点到 n 号点的最短距离。

        如果路径不存在，则输出 impossible。

【数据范围】

        1≤n,m≤105
        图中涉及边长绝对值均不超过 10000

【输入样例】

3 3
1 2 5
2 3 -3
1 3 4

【输出样例】

2

【解题思路】

        SPFA模板题

【Python程序代码】

from collections import *
n, m = map(int, input().split())
g = defaultdict(list)
for _ in range(m):
    x, y, z = map(int, input().split())
    g[x].append((y, z))
inf  = float('inf')
q, vis, dist = deque(), set(),defaultdict(lambda : inf)
q.append(1)
vis.add(1)
dist[1] = 0
while q:
    t = q.popleft()
    vis.remove(t)
    for j, d in g[t]:
        if dist[j] > dist[t] + d:
            dist[j] = dist[t] + d
            if j not in vis:
                vis.add(j)
                q.append(j)
print(dist[n]) if dist[n] < inf / 2 else print("impossible")
 

---

试题四：作物杂交

【题目描述】

        作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号 11 至 N)，第 i 种作物从播种到成熟的时间为 Ti。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 55 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 N 种作物中的一种。初始时，拥有其中  种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A×B→C，A×C→D。则最短的杂交过程为：第 1 天到第 7 天 (作物 B 的时间)，A×B→C第 8 天到第 12 天 (作物 A 的时间)，A×C→D花费 12 天得到作物 D的种子。

【输入格式】

        输入的第 1 行包含 4 个整数 N,M,K,T，N表示作物种类总数 (编号 1 至 N，M 表示初始拥有的作物种子类型数量，K 表示可以杂交的方案数，T 表示目标种子的编号。

        第 2 行包含 N 个整数，其中第 i 个整数表示第 i 种作物的种植时间 Ti。

        第 3 行包含 M 个整数，分别表示已拥有的种子类型 Kj，Kj 两两不同。

        第 4 至 K+3 行，每行包含 3 个整数 A,B,C，表示第 A 类作物和第 B 类作物杂交可以获得第 C 类作物的种子。

【输出格式】

        输出一个整数，表示得到目标种子的最短杂交时间。

【数据范围】

【输入样例】

6 2 4 6
5 3 4 6 4 9
1 2
1 2 3
1 3 4
2 3 5
4 5 6

【输出样例】

16

【解题思路】

        参考：AcWing 3305. 作物杂交(dijkstra/spfa，另类建图) - AcWing

【Python程序代码】

N = 2010
M = 200010
INF = 0x3f3f3f3f
h    = [-1] * N
e    = [0] * M
obj  = [0] * M
ne   = [0] * M
idx  = 0
st   = [False] * N
dist = [INF] * N
q    = [0] * N
hh   = 0
tt   = 0
def push(i):
  global tt
  st[i] = True
  q[tt] = i
  tt += 1
  if tt == N: tt = 0
def pop():
  global hh
  t = q[hh]
  hh += 1
  if hh == N: hh = 0
  st[t] = False
  return t
# a x b -> c
def add(a, b, c):
  global idx
  e[idx] = b
  obj[idx] = c
  ne[idx] = h[a]
  h[a] = idx
  idx += 1
def spfa():
  while hh != tt:
    x = pop()
    i = h[x]
    while i != -1:
      y, z = e[i], obj[i]
      nd = max(dist[x], dist[y]) + max(tm[x], tm[y])
      if dist[z] > nd:
        dist[z] = nd
        if not st[z]: push(z)
      i = ne[i]
 
  return dist[T]
rl = lambda: map(int, input().split())
_, _, k, T = rl()
tm = [0] + list(rl())
for i in rl():
  dist[i] = 0
  push(i)
for _ in range(k):
  a, b, c = rl()
  add(a, b, c)
  add(b, a, c)
print(spfa())