10806  Dijkstra, Dijkstra.
Moderator: Board moderators
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?
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
The idea of your algorithm is wrong. Consider the following test case:
The shortest 1N path is the path 1236 of length 3. However, by taking this path the only possible path for the second prisoner is 1456 of length 300. There is a better solution: paths 126 and 136, total length 22.
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 best algorithm I know of (=the one I implemented during the contest) is O(MN) using BellmanFord.
The idea is as follows:
 replace each edge by two directed arcs
 find the shortest 1N path (using Dijkstra or BellmanFord), 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 1N path (using BellmanFord, 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.)
The idea is as follows:
 replace each edge by two directed arcs
 find the shortest 1N path (using Dijkstra or BellmanFord), 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 1N path (using BellmanFord, 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.)
Yes, you can do it in m lg n by using the algorithm called "successive shortest path" described in these 2 documents :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...
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.

 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 FloydWarshall 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.
Yes, there were no negative cycles. I used FloydWarshall 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!

 Learning poster
 Posts: 77
 Joined: Fri Dec 17, 2004 11:06 am
 Location: East West University, Dhaka, Bangladesh
 Contact:
What does it mean ?
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.
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.
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/
http://groups.yahoo.com/group/acm_solver/

 Experienced poster
 Posts: 123
 Joined: Thu Feb 10, 2005 4:46 am
10806  Dijkstra, Dijkstra.
Hellow everybody, I need more test cases for 10806. I have test
And I have correct anwers, but I get WA at the jugde.
Can you help me whit more dificult cases?
thxxxx!!!
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
Can you help me whit more dificult cases?
thxxxx!!!
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;
}
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;
}
10806critical input output needed
can some one give me some critical input and output for
the problem. 10806Dijkstra, Dijkstra
im suffering from wrong answer for several times.
immediately needed.
tanvir.
the problem. 10806Dijkstra, 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: 10806critical input output needed
What algo are you using? is your algo correct?
Try this inputs:
My AC's output:
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)
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
Code: Select all
Back to jail
909
222
Back to jail
1147
22
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)
My code solved all of the posted testcases in this froum, But i got WA, can anybody post some testcase? I use mincost 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.
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.

 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 counterexample if you find, or some more test cases, thanks
 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 counterexample 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

the world is nothing but a good program, and we are all some instances of the program