3305. 作物杂交
摘要
Title: 3305. 作物杂交
Tag: spfa
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3305. 作物杂交
-
题意
第十一届蓝桥杯省赛第二场C++C/研究生组,第十一届蓝桥杯省赛第二场JAVAC/研究生组
略
-
思路
- 图中的顶点即为作物
- 每条边抽象为
u : 源点, v : 终点, c : 合成点，表示u作物和v作物都已得到的情况下，再花w时间，可以得到c作物, 其中w由题中定义为max(w[s], w[v]) - 最短路径dist定义为得到每种作物需要的最短时间，其中初始时就已有的种子dist为0, 未得到的种子定义为无穷大。
- 对边[u, v, c]的松弛操作为
dist[c] = max(dist[u], dist[v]) + max(w[u], w[v])- 因为得到c首先要得到u和v， 而得到u和v的过程可以同时进行， 所以只需要在其中取最大值即可
- 得到u和v后，再花w时间即可得到c
-
代码
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
42
43
44
45
46
47
48'''
Author: NEFU AB-IN
Date: 2023-03-19 11:26:46
FilePath: \Acwing\3305\3305.py
LastEditTime: 2023-03-19 11:42:51
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations
N = int(2e3 + 10)
INF = int(2e9)
st, w, dist = [0] * N, [0] * N, [INF] * N
g = [[] for _ in range(N)]
q = deque()
def spfa():
while len(q):
u = q.pop()
st[u] = 0
for v, c in g[u]:
if max(dist[u], dist[v]) + max(w[u], w[v]) < dist[c]:
dist[c] = max(dist[u], dist[v]) + max(w[u], w[v])
if st[c] == 0:
st[c] = 1
q.appendleft(c)
n, m, k, t = read()
w[1:] = list(read())
tmp = list(read())
for i in tmp:
q.appendleft(i)
st[i] = 1
dist[i] = 0
for i in range(k):
a, b, c = read()
g[a].append([b, c])
g[b].append([a, c])
spfa()
print(dist[t])