oj.uz

Submission #32119

# Submission time Handle Problem Language Result Execution time Memory
32119 2017-09-27T08:32:52 Z leejseo None (KOI16_gas) Python 2
18 / 100
 532 ms 46 KB 
from heapq import *

MAX_INT = int(9E18)

class Edge(object):
    def __init__(self, to, weight):
        self.to = to
        self.weight = weight

class Node(object):
    def __init__(self, u, dist):
        self.u = u
        self.dist = dist

def dijkstra(V, start, adj_list):
    Q = []
    dist = [MAX_INT for i in range(V)]
    dist[start] = 0
    heappush(Q, [0, Node(start, 0)])
    
    while Q:
        u = Q[0][1].u
        dist_u = Q[0][1].dist
        heappop(Q)
        if dist[u] < dist_u :
            continue
        for i in range(len(adj_list[u])):
            v = adj_list[u][i].to
            dist_v = dist_u + adj_list[u][i].weight
            
            if dist_v < dist[v]:
                dist[v] = dist_v
                heappush(Q, [dist_v, Node(v, dist_v)])
    return dist

def solve(V, graph, oil):
    cost_graph = [ [] for i in range(V)]
    for i in range(V):
        dist = dijkstra(V, i, graph)
        for j in range(V):
            if j == i or dist[j] == MAX_INT :
                continue
            cost = dist[j] * oil[i]
            cost_graph[i].append(Edge(j, cost))
    return dijkstra(V, 0, cost_graph)[V-1]

def main():
    V, E = map(int, raw_input().split())
    graph = [ [] for i in range(V)]
    oil = map(int, raw_input().split())
    for i in range(E):
        fr, to, weight = map(int, raw_input().split())
        fr -= 1
        to -= 1
        graph[fr].append(Edge(to, weight))
        graph[to].append(Edge(fr, weight))
    #r = dijkstra(V, 2, graph)    
    r = solve(V, graph, oil)
    print r
    return
main()

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2 KB Output is correct
2 Correct 16 ms 3 KB Output is correct
3 Correct 16 ms 3 KB Output is correct
4 Correct 16 ms 3 KB Output is correct
5 Correct 15 ms 3 KB Output is correct
6 Correct 14 ms 3 KB Output is correct
7 Correct 15 ms 3 KB Output is correct
8 Correct 14 ms 3 KB Output is correct
9 Correct 14 ms 3 KB Output is correct
10 Correct 14 ms 3 KB Output is correct
11 Correct 15 ms 3 KB Output is correct
12 Correct 16 ms 3 KB Output is correct
13 Correct 15 ms 3 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 46 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 467 ms 46 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2 KB Output is correct
2 Correct 16 ms 3 KB Output is correct
3 Correct 16 ms 3 KB Output is correct
4 Correct 16 ms 3 KB Output is correct
5 Correct 15 ms 3 KB Output is correct
6 Correct 14 ms 3 KB Output is correct
7 Correct 15 ms 3 KB Output is correct
8 Correct 14 ms 3 KB Output is correct
9 Correct 14 ms 3 KB Output is correct
10 Correct 14 ms 3 KB Output is correct
11 Correct 15 ms 3 KB Output is correct
12 Correct 16 ms 3 KB Output is correct
13 Correct 15 ms 3 KB Output is correct
14 Runtime error 532 ms 46 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2 KB Output is correct
2 Correct 16 ms 3 KB Output is correct
3 Correct 16 ms 3 KB Output is correct
4 Correct 16 ms 3 KB Output is correct
5 Correct 15 ms 3 KB Output is correct
6 Correct 14 ms 3 KB Output is correct
7 Correct 15 ms 3 KB Output is correct
8 Correct 14 ms 3 KB Output is correct
9 Correct 14 ms 3 KB Output is correct
10 Correct 14 ms 3 KB Output is correct
11 Correct 15 ms 3 KB Output is correct
12 Correct 16 ms 3 KB Output is correct
13 Correct 15 ms 3 KB Output is correct
14 Runtime error 427 ms 46 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -