10806 - Dijkstra, Dijkstra.

[Martin Macko]

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

Your algo doesn't work for misof's test case posted above. If you remove the edges 1-3 and 2-6 in the third step, you will not find the optimal solution: 1-3-6 and 1-2-6.

[ayon]

misof's test case says
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

if we flow from 1 to 6, maxflow will be 3(i assigned capacity 1 to each edges), there is no way to remove 1-3 or 2-6 at step 3. at step 3 only edge 2-3 will be deleted as no flow occured in edge 2-3, and by running dijkstra twice 1-2-6 and 1-3-6 will be found.

anyway, i found my mistake, thanks for reply

[Neriman]

I keep getting WA for 10806 problem, and my output is correct for any possible input I could think of. Can anyone, PLEASE, help me with some tricky testcases?

[jaracz]

message to misof!!
actually you don't need to use bellman-ford algorithm
at first i got wa ( i used dijkstra then set used arcs as infinity and used dijkstra again) , then i read your advise and used dijkstra then set used arcs as infinity then negated arcs and finally used bellman-ford, i got AC
but..
for curiosity
i tried to use dijkstra instead of bellman-ford and got AC too, with almost 10-times shorter CPU time
i thought dijkstra doesn't work with negative values..
why then?

[mf]

message to misof!!
actually you don't need to use bellman-ford algorithm

Of course, as it's a min-cost max-flow problem. Some of the faster algorithms for it do use Dijkstra instead of Bellman-Ford with help of a clever transformation of the graph. Check nnahas' links.

i thought dijkstra doesn't work with negative values..
why then?

If you let Dijkstra's algorithm to visit the same vertex multiple times (it happens when there are negative weights), then it'll work correctly, as long as there are no negative cycles. But it would hurt its worst case runtime -- there are graphs on which it takes exponential time.
That's why people say that Dijkstra doesn't work with negative weights.

[jaracz]

thx for your explanation
i'll find out more and compare the results, cause problem isn't so hard, so it could be the best way to study;)

regards

[N@$!M]

I have used Dijkstra.
I have Read the Post of Misof in the board But didn't understand How to initialize the cost/weight-matrix .
I have Initialized The Weight-Matrix as follows:
For each edge (a,b) I have set W[a] = W[a] = dist
Then I have (tried to) find the first shortest path using Dijkstra.
Then I have negated the weights of all the edges of this first path.
Then again I have (tried to) Find the next path using Dijkstra.

I got WA.
Help Me.

I Have Checked All the I/Os found on the BOARD.


Here Is My Code:

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#define INF 2147483640
#define num 120

long d[num],p[num] , q_count;

long w[num][num]  , cost;

long dequeue(long Q[])
{
	long item = Q[1] ,i;
	for(i=1;i<q_count;i++)
	{
		Q[i] = Q[i+1] ;	
	}		
	q_count--;
	return item ;
}

void enqueue(long Q[], long item)
{
	long i,j;
	for(i=1;i<=q_count;i++)
	{
		if(d[Q[i]] > d[item] )
		{
			for(j=q_count+1;j>i ;j--)
			{
				Q[j] = Q[j-1] ;	
			}			
			break;	
		}			
	}	
	Q[i] = item ;
	q_count++ ;
}

void Dijkstra(long s,long n)
{
	long i,j  ,Q[num] ,u;
	bool done[num] , inque[num];
	
	for(i=1;i<=n;i++)
	{
		d[i] = INF ;
		p[i] = -1;		
		inque[i] = false;
		done[i] = false;
	}
	
	d[s]  =  0;
	q_count = 0;
	enqueue(Q,s);
	inque[s] = true;
	while(q_count>0)
	{
		u = dequeue(Q);
		
		done[u] = true;
		for(i=1;i<=n;i++)
		{
			if(!done[i])
			{
				if(w[u][i] != INF)
				if( (d[u] + w[u][i]) < d[i])
				{
					d[i] = d[u] + w[u][i];
					p[i] = u;					
					if(!inque[i]){
						enqueue(Q,i);						
						inque[i] = true;
					}
				}					
			}				
		}	
	}	
}

void print_path(long i)
{	
	if(i != 1 )
	{
		if(p[i] == -1)
		{
			cost = INF;
			return;			
		}			
	}
	if(p[i] != -1)
	{
		cost += w[p[i]][i];
		w[p[i]][i] = INF ;
		w[i][p[i]] = 0-w[i][p[i]] ;
		print_path(p[i]);	
		//printf("%ld -- >",p[i]);		
	}	
}

int main(void)
{
	//freopen("10806.txt","r",stdin);
	long i,j,n,e,a,b,dist ,to;
	
	while(scanf("%ld",&n)==1)
	{
		if(n==0) break;
			
		scanf("%ld",&e);
		for(i=1;i<=n;i++)
		{
			for(j=i;j<=n;j++)	
			{
				w[i][j] = w[j][i] = INF;	
			}
		}			
		for(i=1;i<=e;i++)
		{
			scanf("%ld%ld%ld",&a,&b,&dist);
			w[a][b] = dist;	
			w[b][a] = dist;			
		}	
		
		Dijkstra(1,n);	
		
		cost = 0;
		print_path(n);		
		//printf("%ld\n Cost = %ld\n",n,cost);
		Dijkstra(1,n);
		print_path(n);
		
		if(cost < INF)
			printf("%ld\n",cost);
			//printf("%ld\n%ld\n",p[i],cost);			
		else 
			printf("Back to jail\n");
	}
}

[mmonish]

>> N@$!M

Are u sure that the dijkstra will work for finding the second shortest path?
Use Bellmanford algorithm to find the second shortest path bcoz edge weights r negetive.

Hope this helps.

[asmaamagdi]

Hey guys.
I'm getting lots of WAs to this problem though I think my algo is right.

I first use dijkstra to find the first shortest path.
Then I mark each of its edges as invalid edges.
I use dijkstra again and use only valid edges this times.

This gave me WAs

The only bug I thought of was that I didn't mark the inverse edges as invalid edges. (if the first path contains edge 2 3, then I can't use 3 2 in the second path).
I modified my code to mark the inverse of the edges too but still WA

Please someone tells me if my idea is right or wrong.
and can someone please explain to me where the negative weighted edges are, or why you make any edge a negative weighted edge. How could this help ??!!

Thanx in advance

[jaracz]

Read carefully entire topic, there's a critical input above for your algo, which let you know why your idea is wrong..