Page 1 of 2

10806 - Dijkstra, Dijkstra.

Posted: Thu Jan 13, 2005 11:10 am
by TISARKER
Is there any critical input for this problem?
If yes , So please give me that input.
My algorithm is for a sigle input:
1.Find all pairs shortest path after loading input.
2.If there exists any path from node 1 to n
a.Store its cost .
b.Close all the path from node 1 to n.
Otherwise print "Back to Jail".return.
3.Find all pairs shortest path.
4.If there exists any path from node 1 to n
a.Store its cost .
Otherwise print "Back to Jail".return.
5.Print cost1+cost2.return.
Is my Algorithm correct?

Posted: Thu Jan 13, 2005 2:35 pm
by misof
The idea of your algorithm is wrong. Consider the following test case:

Code: Select all

6
8
1 2 1
2 3 1
3 6 1
1 4 100
4 5 100
5 6 100
1 3 10
2 6 10
The shortest 1-N path is the path 1-2-3-6 of length 3. However, by taking this path the only possible path for the second prisoner is 1-4-5-6 of length 300. There is a better solution: paths 1-2-6 and 1-3-6, total length 22.

Posted: Fri Jan 14, 2005 12:41 am
by Monsoon
I've written an AC program but i works in O(n^2*m*log n), i wonder how i can do it quicker. Is there exist any special algo to do it or it is a special combination of dijkstra algos...

Posted: Fri Jan 14, 2005 1:48 am
by misof
The best algorithm I know of (=the one I implemented during the contest) is O(MN) using Bellman-Ford.

The idea is as follows:
- replace each edge by two directed arcs
- find the shortest 1-N path (using Dijkstra or Bellman-Ford), remember its cost COST1
- replace the cost for all its arcs by INFINITY (you may not use them again)
- negate the cost for all their twin arcs (i.e. the arcs along the path in the opposite direction)
- find the shortest 1-N path (using Bellman-Ford, as now there are edges with negative cost), remember its cost COST2
- return COST1 + COST2

Idea of the proof:
- The adjusted graph contains no negative cycles, because the first selected path was the shortest one.
- When searching for the second path, using an edge from the first path in an opposite direction corresponds to deleting this edge from the final solution. (This is similar to finding an augmenting path in network flow algorithms. Try drawing a picture, e.g. for the test case I posted above, if this idea is hard to grasp.)

Posted: Fri Jan 14, 2005 1:54 am
by nnahas
Monsoon wrote:I've written an AC program but i works in O(n^2*m*log n), i wonder how i can do it quicker. Is there exist any special algo to do it or it is a special combination of dijkstra algos...
Yes, you can do it in m lg n by using the algorithm called "successive shortest path" described in these 2 documents :

http://ocw.mit.edu/NR/rdonlyres/Electri ... ribe13.pdf

http://ocw.mit.edu/NR/rdonlyres/Electri ... ribe14.pdf

You must read the first to understand the second

another description , perhaps more friendly, of the same algo, can be found here:

http://www.core.org.cn/NR/rdonlyres/Slo ... stpath.pdf

Although this algorithm runs in O(n^2 lgn U) in the general case where U is the maximum capacity of an edge, in this case it runs in m lgn because there are only 2 augmentations to do, and all edges have the same capacity equal to 1.

Posted: Fri Jan 14, 2005 1:49 pm
by Monsoon
thx

Posted: Wed Feb 16, 2005 4:53 pm
by Destination Goa
I used two maximum flow iterations. Edges with f[j]==0 have cost c[j] (we will use them if we decide to follow). Edges with f[j]==-1 have cost -c[j] (we will eliminate them if we decide to follow). Edges with f[j]==1 can't be used. On both iterations I searched for augmenting flow path of minimal cost and used it.

Yes, there were no negative cycles. I used Floyd-Warshall since it's also O(N^3), but a little easier to write. M = O(N^2) for this problem.

The general solution will be finding any max flow and then searching for negative cost circuits, but it's O(N^5) algorithm due to possible number of such cycles after careless maxflow.

Posted: Thu Apr 07, 2005 6:12 pm
by Niaz
What does it mean ?

Code: Select all

Problem, in short
Given a weighed, undirected graph, find the shortest path from 
S to T and back without using the same edge twice.
Please, make me clear about the things that problem talks and about the things that programmers talk!

At first I thought in the way of TISARKER. But then I started to think like misof. But finaly the above line make me totally puzzeled! Please help me.

Thanks in advance.

Posted: Fri Apr 08, 2005 10:22 am
by Destination Goa
You have to find 2 paths from S to T, such that they don't share any edge (but may share some nodes). Sum of their lengths must be minimal possible.

10806 - Dijkstra, Dijkstra.

Posted: Mon Apr 25, 2005 12:31 pm
by tobal
Hellow everybody, I need more test cases for 10806. I have test

Code: Select all

6
8
1 2 1
2 3 1
3 6 1
1 4 100
4 5 100
5 6 100
1 3 10
2 6 10
And I have correct anwers, but I get WA at the jugde. :-?

Can you help me whit more dificult cases?

thxxxx!!!

10806 - help! WA!

Posted: Sun May 01, 2005 9:43 pm
by medv
I tested a lot, but WA.
Help me please!

#include <stdio.h>
#include <limits.h>
#include <memory.h>
const int MAX = 101;

int i,n,m,res;
int b,e,dist;
int mas[MAX][MAX];
int used[MAX],d[MAX];
int next[MAX];

int dejkstra(void)
{
int i,j,min,ptr;
memset(next,-1,sizeof(next));
memset(used,0,sizeof(used));
memset(d,63,sizeof(d));
d[1] = 0;
for(i=1;i<n;i++)
{
min = INT_MAX / 2; ptr = -1;
for(j=1;j<=n;j++)
if (!used[j] && d[j] < min) {min = d[j]; ptr = j;}
if (ptr == -1) return d[n];
for(j=1;j<=n;j++)
if (!used[j] && (d[j] > d[ptr]+mas[ptr][j]))
{
d[j] = d[ptr]+mas[ptr][j];
next[j] = ptr;
}
used[ptr] = 1;
}
return d[n];
}

int main(void)
{
while(scanf("%d %d",&n,&m) == 2)
{
memset(mas,63,sizeof(mas));
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&b,&e,&dist);
mas[b][e] = mas[e][b] = dist;
}
res = dejkstra();
if (res > INT_MAX / 3)
{
printf("Back to jail\n"); continue;
}
i = n; while(i != 1)
{
mas[i][next[i]] = -mas[next[i]][i];
mas[next[i]][i] = INT_MAX / 2;
i = next[i];
}
res += dejkstra();
if (res < INT_MAX / 3) printf("%d\n",res);
else printf("Back to jail\n");
}
return 0;
}

10806-critical input output needed

Posted: Wed Aug 31, 2005 12:18 pm
by tanvir
can some one give me some critical input and output for
the problem. 10806-Dijkstra, Dijkstra

im suffering from wrong answer for several times.
immediately needed. :o
tanvir.

Re: 10806-critical input output needed

Posted: Wed Aug 31, 2005 10:03 pm
by Martin Macko
What algo are you using? is your algo correct?

Try this inputs:

Code: Select all

5
4
1 4 47
4 2 13
3 2 15
5 3 4
8
12
1 2 745
1 7 998
2 8 177
1 3 129
1 4 157
5 8 124
1 5 487
1 6 999
3 8 478
4 8 145
6 8 854
7 8 768
4
4
4 2 65
1 2 25
3 4 74
1 3 58
10
13
1 7 158
2 7 999
3 10 998
4 5 997
5 9 996
5 3 995
1 8 994
9 10 993
5 2 992
1 6 999
2 6 999
2 8 999
4 10 998
5
10
4 3 895
3 5 485
4 5 217
5 1 785
3 2 147
5 2 856
4 2 175
1 2 578
1 3 745
4 1 145
6
8
1 2 1
2 3 1
3 6 1
1 4 100
4 5 100
5 6 100
1 3 10
2 6 10
0
My AC's output:

Code: Select all

Back to jail
909
222
Back to jail
1147
22
Or try some large inputs with 100 nodes.

Btw, in the future, please, try to use the an existing topic on a problem if there is one. (There are few on 10806 already)

Posted: Fri Aug 04, 2006 8:45 pm
by Moha
My code solved all of the posted testcases in this froum, But i got WA, can anybody post some testcase? I use min-cost maximum flow algorithm.
This is my approach:
I assign 1 capacity to each edge, so each edge has 1 capacity and also a length. I use a maxflow algorithm on, with a little modification. for finding an augmenting path I use a dijkstra algorithm to find a path with a minimum length. I want just two to these such a path. the anser to this problem is sum of all edge costs in which there is a flow in it.
am I correct? My code passed all of posted testcase not just in this thread. My method is very similar to Misof`s method.

Posted: Mon Aug 21, 2006 1:48 pm
by ayon
can anyone verify whether my algorithm is correct? i am getting wa, i checked all inputs posted in this board.

- assign capacity 1 to each edges of the graph and simply run maxflow
- if maxflow < 2 then Back to jail
- remove edges where no flow occured(i.e where still have residual capacity)
- run dijkstra, get cost1
- remove dijkstra edges
- run dijkstra again, get cost2
- output cost1+cost2

please give me some counter-example if you find, or some more test cases, thanks