fork download 
  1. # Author : prayushd
  2. # Language : Python
  3.  
  4. import re
  5. import os
  6. import sys
  7. from random import randint
  8. from datetime import datetime
  9. from functools import reduce
  10. from math import ceil, inf, floor
  11. from fractions import gcd
  12. from queue import Queue
  13. from heapq import heapify, heappush, heappop
  14. from collections import defaultdict, Counter, deque
  15. from bisect import bisect, insort, bisect_left, bisect_right
  16.  
  17. mod = int(1e9)+7
  18. mod_ = 998244353
  19. MAX = int(1e5)+1
  20. input = sys.stdin.readline
  21.  
  22. '''
  23. Check for special cases (n=1)
  24. One wrong submission = 10 mins penalty!
  25. do smth instead of nothing and stay organized
  26. '''
  27.  
  28. graph = defaultdict(list)
  29. edges = dict()
  30.  
  31. def shortest_path(start, end, n):
  32. 	dist = [inf]*(n+1)
  33. 	dist[start] = 0
  34. 	parent = [None]*(n+1)
  35.  
  36. 	q = [(0, start)]
  37. 	heapify(q)
  38. 	while q:
  39. 		x, u = heappop(q)
  40. 		for child in graph[u]:
  41. 			v, _ = child
  42. 			d = edges[tuple(sorted([u, v]))]
  43. 			if dist[u] + d < dist[v]:
  44. 				dist[v] = dist[u] + d
  45. 				parent[v] = u
  46. 				heappush(q, (dist[v], v))
  47.  
  48. 	path = []
  49. 	while True:
  50. 		path.append(end)
  51. 		if parent[end] is None:
  52. 			break
  53. 		end = parent[end]
  54.  
  55. 	path = path[::-1]
  56. 	return path
  57.  
  58.  
  59. def main():
  60. 	for _ in range(int(input())):
  61. 		graph.clear()
  62. 		edges.clear()
  63. 		n, m = map(int, input().split())
  64. 		src, des, mid = map(int, input().split())
  65. 		for i in range(m):
  66. 			u, v, w = map(int, input().split())
  67. 			edges[tuple(sorted([u, v]))] = w
  68. 			graph[u].append((v, w))
  69. 			graph[v].append((u, w))
  70. 		total = 0
  71. 		path1 = shortest_path(src, mid, n)
  72. 		for i in range(1, len(path1)):
  73. 			total += edges[tuple(sorted([path1[i], path1[i-1]]))]
  74. 			edges[tuple(sorted([path1[i], path1[i-1]]))] = 0
  75. 		path2 = shortest_path(mid, des, n)
  76.  
  77. 		for i in range(1, len(path2)):
  78. 			total += edges[tuple(sorted([path2[i], path2[i-1]]))]
  79.  
  80. 		print(total)
  81.  
  82.  
  83. if __name__ == '__main__':
  84. 	main()
Success #stdin #stdout 0.03s 13492KB
comments ()
stdin 
2
4 3
1 3 4
1 2 1
2 3 2
2 4 3
4 3
1 1 4
1 2 1
2 3 2
2 4 3
stdout 
6
4
https://ideone.com/gLjaZk
language:
Python 3 (python  3.12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!