Submission #32119

#	Time	Username	Problem	Language	Result	Execution time	Memory
32119		leejseo	주유소 (KOI16_gas)	Cpython 2	18 / 100	532 ms	46 KiB

gas

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 / 18
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27