For everyone got TLE (the time limits are very strict).
I implemented the dijkstra by priority_queue and got TLE with testcase 7 and 8. After that, I added an array visited[] to mark all the vertices which has been visited, so I can skip update adjacent vertices (dense graph).
I still got TLE with testcase 8. So I change the distance from long long to int (which can be applied for this problem) and got AC. I didn't think that could work :)).
Read more… (83 words)