81 lines
1.7 KiB
Swift
81 lines
1.7 KiB
Swift
import Foundation
|
|
|
|
final class FileIO {
|
|
private let buffer:[UInt8]
|
|
private var index: Int = 0
|
|
|
|
init(fileHandle: FileHandle = FileHandle.standardInput) {
|
|
|
|
buffer = Array(try! fileHandle.readToEnd()!) + [UInt8(0)]
|
|
}
|
|
|
|
@inline(__always) private func read() -> UInt8 {
|
|
defer { index += 1 }
|
|
return buffer[index]
|
|
}
|
|
|
|
@inline(__always) func readInt() -> Int {
|
|
var sum = 0
|
|
var now = read()
|
|
var isPositive = true
|
|
|
|
while now == 10 || now == 32 { now = read() }
|
|
if now == 45 { isPositive = false; now = read() }
|
|
|
|
while now >= 48, now <= 57 {
|
|
sum = sum * 10 + Int(now-48)
|
|
now = read()
|
|
}
|
|
|
|
return sum * (isPositive ? 1 : -1)
|
|
}
|
|
}
|
|
|
|
let input = FileIO()
|
|
var ans: [String] = []
|
|
|
|
func solve() -> String {
|
|
let (N, K) = (input.readInt(), input.readInt())
|
|
|
|
var build_time: [Int] = [0]
|
|
for _ in 0..<N {
|
|
build_time.append(input.readInt())
|
|
}
|
|
|
|
var pre_build_info: [[Int]] = Array(repeating: [], count: N+1)
|
|
for _ in 0..<K {
|
|
let (X, Y) = (input.readInt(), input.readInt())
|
|
pre_build_info[Y].append(X)
|
|
}
|
|
|
|
let W = input.readInt()
|
|
|
|
var dp: [Int] = Array(repeating: -1, count: N+1)
|
|
|
|
func build(_ n: Int) -> Int {
|
|
if dp[n] == -1 {
|
|
var total_time = 0
|
|
for prev in pre_build_info[n] {
|
|
total_time = max(total_time, build(prev))
|
|
}
|
|
dp[n] = total_time + build_time[n]
|
|
}
|
|
|
|
return dp[n]
|
|
}
|
|
|
|
return String(build(W))
|
|
}
|
|
|
|
func main() {
|
|
let T = input.readInt()
|
|
|
|
for _ in 0..<T {
|
|
ans.append(solve())
|
|
}
|
|
|
|
print(ans.joined(separator: "\n"))
|
|
}
|
|
|
|
main()
|