TSHPATH  The TurtleĀ“s Shortest Path
Given a list of cities. Each direct connection between two cities has its transportation cost (an integer bigger than 0). The goal is to find the paths of minimum cost between pairs of cities. Assume that the cost of each path (which is the sum of costs of all direct connections belongning to this path) is at most 200000. The name of a city is a string containing characters a,...,z and is at most 10 characters long.
Input
s [the number of tests <= 10] n [the number of cities <= 10000] NAME [city name] p [the number of neighbours of city NAME] nr cost [nr  index of a city connected to NAME (the index of the first city is 1)] [cost  the transportation cost] r [the number of paths to find <= 100] NAME1 NAME2 [NAME1  source, NAME2  destination] [empty line separating the tests]
Output
cost [the minimum transportation cost from city NAME1 to city NAME2 (one per line)]
Example
Input: 1 4 gdansk 2 2 1 3 3 bydgoszcz 3 1 1 3 1 4 4 torun 3 1 3 2 1 4 1 warszawa 2 2 4 3 1 2 gdansk warszawa bydgoszcz warszawa Output: 3 2Warning: large Input/Output data, be careful with certain languages
hide comments
nadstratosfer:
20180222 06:57:22
A copy of a classical problem with a lenient TL would be a great idea to experiment with optimizations, unfortunately with the limit recalculated after the cluster change it's as useless for Python as its classical version :/


iharsh234:
20160708 22:16:06
optimisation overkilled AC in 0.45 sec 

samarsingh:
20160615 11:39:37
WA after testing every possible test cases available in the comments or on the internet...http://ideone.com/Ub4zCd


aexpo:
20160607 16:44:24
1.39 sec :) 

rraj001:
20160531 05:56:15
do not forget to clear your adjacency array aftere very test case,just costed me 3 WA's 

ranjanakash166:
20160528 11:40:00
SAME PROBLEM AS


pratika:
20151220 20:17:06
1. Hashmap for obtaining the indexes of source and destination.


bholagabbar:
20150421 19:41:02
Goddamn TLE :( Anyways to optimize in JAVA? 

Mahesh Kohli:
20150408 13:52:14
can someone give a test case where we can get a possible seg fault 

Arafat dad Khan:
20150301 14:25:35
Ac After 40 Wcs Best Feeling in the world 
Added by:  mima 
Date:  20041021 
Time limit:  5.659s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  DASM Programming League 2003 (thanks to Darek Dereniowski) a copy of SHPATH problem with 60s time limit 