## 10806 - Dijkstra, Dijkstra.

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

### 10806 - Dijkstra, Dijkstra.

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?
Mr. Arithmetic logic Unit

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
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...

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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.)

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm
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.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland
thx

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
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.
To be the best you must become the best!

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:
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.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am
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.
To be the best you must become the best!

tobal
New poster
Posts: 1
Joined: Mon Apr 25, 2005 12:27 pm

### 10806 - Dijkstra, Dijkstra.

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

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

### 10806 - help! WA!

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;
}

tanvir
New poster
Posts: 22
Joined: Wed Aug 31, 2005 12:09 pm

### 10806-critical input output needed

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.
tanvir.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: 10806-critical input output needed

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)

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
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.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh
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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program