Problem Code: INOI1402
If you can write the problem code, why not give the direct link to us? A link is a LOT more convenient to people who are trying to help you. A LOT.
Dijkstra’s algorithm is used to find the shortest path between a source and all the other vertices.
But, in this question, you are supposed to find the shortest path between all the pairs of vertices. This is done by using Floyd-Warshall algorithm, with a complexity of O(N^3).
Since, N = 230, a O(N^3) algorithm will run well within the time limit.
You can read about Floyd-Warshall algorithm in the following link.
P.S. You can also use Dijkstra’s algorithm taking each vertex as a source. However, in this case, using Floyd-Warshall algorithm is much simpler and concise.
can anyone explain what should b d output for dat problem ?? i mean what needs to found out ?? im unable to understand d output expected !!
Let cost[i][j] denote the minimum cost to go from city i to city j (whether directly or indirectly). You have to find the maximum of cost[i][j] for all 1 <= i,j <= C.
so…we need to find d cheapest routes for all pairs of cities and among dat cheapest routes we need to output d max.cheapest route …ri8 ?
got it !! thnks fr ua help @c_utkarsh
Can someone please help me with my solution for this problem. I have just used Floyd algorithm but getting almost all the ans WA, don’t know the reason. Thanks,
Here is my solution link
link to ur code is unaccessable !! pls provide another link !
It should have been accessible , i don’t know the reason but here is the code on ideone. Please have a look at it and let me know if there is any problem.
given graph is an undirected graph…! But u have mistook it as directed !
as well as a[y][x] is also equal to p !!
@vishesh_345 this is an undirected graph,so if cost from u to v is w then cost from v to u is also w.add a[y][x]=p to your code after scanning x,y,p on line 18
Guys , i can’t figure out whats wrong with my code. I have used Floyd Warshall’s algorithm. Help anyone ?