do problem free ticket based on dijkstra's algorithm

general
1

Problem Code: INOI1402

2

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.

2 Likes
3

https://www.codechef.com/IOIPRAC/problems/INOI1402

4

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.

2 Likes
5

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 !!

6

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.

7

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 ?

8

got it !! thnks fr ua help @c_utkarsh

9

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

10

link to ur code is unaccessable !! pls provide another link !

11

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.

Link: https://ideone.com/aIOUXF

12

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 !!

1 Like
13

@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

1 Like
14

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 :slight_smile:

15

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

Code : https://pastebin.com/6HQYiUEV