Участник:Kozub/Highways

Материал из DISCOPAL
Перейти к: навигация, поиск

Ссылка на задачу на spojcode: https://www.spoj.com/problems/HIGHWAYS/

import queue
from collections import defaultdict
 
class Vertex:
    def __init__(self,p,i):
        self.priority = p
        self.item = i
    def __lt__(self,v):
        return self.priority < v.priority
 
def Dijkstra(n, graph, start=0, end=0):
    visited = set()
    deepth = dict({start : Vertex(0,start)})
    q = queue.PriorityQueue()
    q.put(deepth[start])
 
    while not q.empty():
        s = q.get().item
 
        if s == end:
            return max(deepth[s].priority,0)
 
        if s not in visited:
            for node,dist in graph[s]:
                if node in deepth:
                    deepth[node].priority = min(deepth[node].priority, deepth[s].priority  + dist)
                else:
                    v =  Vertex(deepth[s].priority  + dist, node)
                    deepth[node] = v
                    q.put(v)
 
    return'NONE'
 
 
 
k = int(input())
for i in range(k):
    n, m, start, end = list(map(int,input().split()))
 
    graph = defaultdict(set)
    for i in range(m):
        a, b, r = list(map(int, input().split()))
        graph[a].add((b,r))
        graph[b].add((a,r))
 
    print(Dijkstra(n, graph, start, end))