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.

http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/

**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 ?

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

https://www.codechef.com/viewsolution/14297004

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 !

cin>>x>>y>>p;

a[x][y]=p;

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

I was thinking in a wrong direction (thought WA was due to some overflow). Yes, it’s a directed one and we have to store in both. Thanks a lot @hruday968 and @msd_007

Guys , i can’t figure out whats wrong with my code. I have used Floyd Warshall’s algorithm. Help anyone ?