class Graph: def __init__(self, n, directed=False, decrement=True, edges=[]): self.n = n self.directed = directed self.decrement = decrement self.edges = [[] for _ in range(self.n)] for x, y, cost in edges: self.add_edge(x, y, cost) def add_edge(self, x, y, cost): if self.decrement: x -= 1 y -= 1 self.edges[x].append((y, cost)) if self.directed == False: self.edges[y].append((x, cost)) def dijkstra(self, start=None, INF=10**18): """ 返り値は 0-indexed !!! :param start: スタート地点 :return: スタート地点から各点への距離のリスト 備考: heqpq の比較のための key は第一引数である点に注意( = heappush(heapq, (key,value)) ) """ res = [INF] * self.n if start is None: start=self.decrement start=start-self.decrement res[start] = 0 next_set = [(0, start)] parents=[-1]*N while next_set: dist, p = heappop(next_set) if res[p] < dist: continue """ここで頂点pまでの最短距離が確定。よって、ここを通るのはN回のみ""" for q, cost in self.edges[p]: temp_d = dist + cost if temp_d < res[q]: res[q] = temp_d parents[q] = p heappush(next_set, (temp_d, q)) return res, parents def draw(self): """ :return: グラフを可視化 """ import matplotlib.pyplot as plt import networkx as nx if self.directed: G = nx.DiGraph() else: G = nx.Graph() for x in range(self.n): for y, cost in self.edges[x]: G.add_edge(x + self.decrement, y + self.decrement, weight=cost) edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)} pos = nx.spring_layout(G) nx.draw_networkx(G, pos, with_labels=True, connectionstyle='arc3, rad = 0.1') nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels) plt.axis("off") plt.show() ######################################################### def example(): global input example = iter( """ 3 3 1 2 1 1 3 1 2 3 3 """ .strip().split("\n")) input = lambda: next(example) def example2(): global input example = iter( """ 6 9 1 2 7 2 3 10 1 3 9 1 6 14 3 6 2 5 6 9 4 5 6 2 4 15 3 4 11 """ .strip().split("\n")) input = lambda: next(example) ######################################################### import sys from heapq import * input = sys.stdin.readline INF = 10**18 # 大きい数字 N, M, P, Q, T = map(int, input().split()) graph = Graph(N, directed=False, decrement=True) for _ in range(M): x, y, cost = map(int, input().split()) graph.add_edge(x, y, cost) dist, par = graph.dijkstra(start=1,INF=INF) distP, parP = graph.dijkstra(start=P,INF=INF) distQ, parQ = graph.dijkstra(start=Q,INF=INF) res=-1 for i in range(N): off = dist[i]*2 t1 = distP[i] t2 = distQ[i] t=max(t1,t2)*2 if off+t>T: continue res=max(T-t,res) if t1>t2: g=i while g!=-1: tp=t1-distP[g] if off+tp*2+t2*2<=T: res=max(T-distP[g]*2,res) g=parP[g] else: g=i while g!=-1: tp=t2-distQ[g] if off+tp*2+t1*2<=T: res=max(T-distQ[g]*2,res) g=parQ[g] print(res)