Submission #17661476

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func readInt3(line: Int = #line, file: String = #file) -> (Int, Int, Int) {
    guard let string = readLine() else {
        preconditionFailure("No input (at line \(line) in \(file))")
    }
    let values: [Int] = string.split(separator: " ").map { part in
        guard let value = Int(part) else {
            preconditionFailure("Illegal input value: \(string) (at line \(line) in \(file))")
        }
        return value
    }
    precondition(values.count == 3, "Illegal number of input values: count = \(values.count), values = \(values) (at line \(line) in \(file))")
    return (values[0], values[1], values[2])
}
func readIntN(line: Int = #line, file: String = #file) -> [Int] {
    guard let string = readLine() else {
        preconditionFailure("No input (at line \(line) in \(file))")
    }
    let values: [Int] = string.split(separator: " ").map { part in
        guard let value = Int(part) else {
            preconditionFailure("Illegal input value: \(string) (at line \(line) in \(file))")
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

func readInt3(line: Int = #line, file: String = #file) -> (Int, Int, Int) {
    guard let string = readLine() else {
        preconditionFailure("No input (at line \(line) in \(file))")
    }
    let values: [Int] = string.split(separator: " ").map { part in
        guard let value = Int(part) else {
            preconditionFailure("Illegal input value: \(string) (at line \(line) in \(file))")
        }
        return value
    }
    precondition(values.count == 3, "Illegal number of input values: count = \(values.count), values = \(values) (at line \(line) in \(file))")
    return (values[0], values[1], values[2])
}

func readIntN(line: Int = #line, file: String = #file) -> [Int] {
    guard let string = readLine() else {
        preconditionFailure("No input (at line \(line) in \(file))")
    }
    let values: [Int] = string.split(separator: " ").map { part in
        guard let value = Int(part) else {
            preconditionFailure("Illegal input value: \(string) (at line \(line) in \(file))")
        }
        return value
    }
    return values
}

private struct _PriorityQueue<Element> {
    private var elements: [Element] = []
    private let areInIncreasingOrder: (Element, Element) -> Bool
    
    init<S>(_ elements: S, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) where S: Sequence, S.Element == Element {
        self.areInIncreasingOrder = areInIncreasingOrder
        for element in elements {
            append(element)
        }
    }
    
    init(by areInIncreasingOrder: @escaping (Element, Element) -> Bool) {
        self.init(EmptyCollection(), by: areInIncreasingOrder)
    }
    
    var isEmpty: Bool { elements.isEmpty }
    var count: Int { elements.count }
    var first: Element? { elements.first }
    
    mutating func append(_ element: Element) {
        var i = elements.count
        elements.append(element)
        elements.withUnsafeMutableBufferPointer { elements in
            while i > 0 {
                let parentIndex = (i - 1) >> 1
                let parent = elements[parentIndex]
                guard areInIncreasingOrder(element, parent) else { break }
                elements[parentIndex] = element
                elements[i] = parent
                i = parentIndex
            }
        }
    }
    
    mutating func popFirst() -> Element? {
        guard let element = elements.popLast() else { return nil }
        guard let first = elements.first else { return element }
        
        elements.withUnsafeMutableBufferPointer { elements in
            elements[0] = element
            
            var  i = 0
            while true {
                var childIndex: Int = (i << 1) + 1
                guard childIndex < elements.count else { break }
                var child: Element = elements[childIndex]
                let rightIndex = childIndex + 1
                if rightIndex < elements.count {
                    let right = elements[rightIndex]
                    if areInIncreasingOrder(right, child) {
                        childIndex = rightIndex
                        child = right
                    }
                }
                if areInIncreasingOrder(element, child) { break }
                elements[childIndex] = element
                elements[i] = child
                i = childIndex
            }
        }

        return first
    }
}
protocol HasInfinity {
    static var infinity: Self { get }
}
extension Int: HasInfinity { static var infinity: Int { .max } }
extension UInt: HasInfinity { static var infinity: UInt { .max } }
extension Float: HasInfinity {}
extension Double: HasInfinity {}
func dijkstra<Distance>(graph: [[(index: Int, distance: Distance)]], startedAt start: Int) -> [Distance] where Distance: Comparable, Distance: AdditiveArithmetic, Distance: HasInfinity {
    var result: [Distance] = .init(repeating: .infinity, count: graph.count)
    result[start] = .zero
    var used = Array(repeating:false, count: graph.count)
    var queue = _PriorityQueue<(Distance, Int)>(by: <=)
    queue.append((.zero, start))
    while let (_, from) = queue.popFirst() {
        if used[from] { continue }
        used[from] = true
        for (to, distance) in graph[from]{
            if result[from] + distance < result[to] {
                result[to] = result[from] + distance
                queue.append((result[to], to))
            }
        }
    }
    return result
}

let (n, m, t) = readInt3()
let aa = readIntN()

var graph1: [[(index: Int, distance: Int)]] = .init(repeating: [], count: n)
var graph2: [[(index: Int, distance: Int)]] = .init(repeating: [], count: n)
for _ in 1 ... m {
    let (a, b, c) = readInt3()
    graph1[a - 1].append((index: b - 1, distance: c))
    graph2[b - 1].append((index: a - 1, distance: c))
}

let distances1 = dijkstra(graph: graph1, startedAt: 0)
let distances2 = dijkstra(graph: graph2, startedAt: 0)

var maxMoney: Int = .min
for i in 0 ..< n {
    if distances1[i] == Int.max || distances2[i] == Int.max{
        continue
    }
    let money = aa[i] * (t - distances1[i] - distances2[i])
    if money > maxMoney { maxMoney = money }
}

print(maxMoney)

Submission Info

Judge Result