10806 - Dijkstra, Dijkstra.

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

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

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

[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.)

[nnahas]

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]

thx

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

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

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

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

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

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

[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)

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

[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