10354 - Avoiding Your Boss

[amitc]

This problem looked easy and I attempted the following to solve it,

1) Found the shortest path of the boss home to office using all pair shortest path and then removed the shortest route (made the distance to these vertices as infinity) from the graph.
2) In the new map, tried to find the shortest path of home to market and checked if it was infinity, in which case I would display "MISSION IMPOSSIBLE." otherwise the distance.
(I assumed the shortest route cost was what the problem required for output?)
3) Additionally I checked for any self loops and removed them.

Is my method wrong or am I missing something?

Thanks,
Amit

[shahriar_manzoor]

Did you consider the case when The market, boss's office and your home are in same place and any other such terminal case?

[Adrian Kuegel]

1) Found the shortest path of the boss home to office using all pair shortest path and then removed the shortest route (made the distance to these vertices as infinity) from the graph.

Did you consider that there can be more than one shortest path from boss home to office? You have to find all nodes lying on a shortest path.

[Even]

6 8 2 3 1 4
1 2 4
2 3 4
3 5 1
3 6 1
2 5 3
1 5 10
5 6 10
6 4 10

if input like above...what should be the output...

please run it ...not draw it... thanks in advance

[Adrian Kuegel]

As you said, I haven't drawn it, only used my accepted program, but you know that accepted doesn't mean correct and I have not verified the correctness of this output.
Set #1
?
Set #2
?

[shahriar_manzoor]

Adrian I think u have produced output of another program . The correct output is

MISSION IMPOSSIBLE.

[Even]

6 8 2 3 1 4
1 2 4
2 3 4
3 5 1
3 6 1
2 5 3
1 5 10
5 6 10
6 4 10

ya...it should be MISSION IMPOSSIBLE.

yesterday..I accepted it...but I think this is an important test case ...

so I add it in my 10354.in and run my AC program again...

but .. it give me the answer 30

I modify my program and get the answer MISSION IMPOSSIBLE.

but WA on judge ...so I post for asking...

now, I find my mistake and correct it and got AC again ..
and maybe the testcase should be more compelete

[amitc]

i had completely forgotten about multiple shortest paths. After I realized the same, I modified my code into a djikstra's single source shortest path program with every node having a predecessor list. This got accepted by the judge.

On a side note, is there any way to recover all shortest paths from all pair shortest path algorithm ? I couldn't figure out how to do this so switched to djikstra.

[Adrian Kuegel]

Yes, I noticed now that I was using my program for 10356, sorry. It would have been better if I had drawn it :-)
Btw, the right program produces also MISSION IMPOSSIBLE.

[minhaz]

hello i got time limit exit in that problem.can anyone help me how can i make the problem efficient.


i add my source code here.i first use all pair shortest path algorithm and use recursion to cut all shortest path of boss then use single pair shortest path algorithm to find out the result


[c]
#include<stdio.h>
#include<string.h>

int w[102][102],track[102];
int P,BH,OF,we[102];
char path[102][102],temp[102][102],used[102],flag[102];

void recursion(int bh,double sum,int k)
{
int i,j,m;
if(sum>w[BH][OF])
return;
if(bh==OF && sum==w[BH][OF])
{
for(j=0;j<k;j++)
{
for(m=1;m<=P;m++)
{
temp[m][track[j]]=0;
temp[track[j]][m]=0;
}
flag[track[j]]=1;
}
return;
}
for(i=1;i<=P;i++)
{
if(path[bh]==0 || used==1)
continue;
used=1;
track[k]=i;
recursion(i,sum+w[bh],k+1);
used=0;
track[k]=0;
}
}

void initialize(int s)
{
int i;
for(i=0;i<=P;i++)
we=9999;
we[s]=0;
}

void relax(int u,int v)
{
if(we[v]>w[v]+we)
we[v]=w[v]+we;
}

void dijkstra(int s)
{
char dummy[102];
int i,u,v,min;
memset(dummy,1,sizeof(dummy));
dummy[P+1]='\0';
initialize(s);
while(strcmp(flag,dummy)!=0)
{
min=9999;
for(i=1;i<=P;i++)
{
if(flag==1)
continue;
if(min>we)
{
min=we;
u=i;
}
}
if(min==9999)
break;
flag=1;
for(v=1;v<=P;v++)
if(temp[v]==1 && flag[v]==0)
relax(u,v);
}
}

void main()
{
int i,j,k,R,YH,M,u,v,d;

while(scanf("%d",&P)==1)
{
scanf("%d%d%d%d%d",&R,&BH,&OF,&YH,&M);

for(i=1;i<=P;i++)
for(j=1;j<=P;j++)
w[j]=9999;

memset(path,0,sizeof(path));
memset(temp,0,sizeof(temp));
for(i=0;i<R;i++)
{
scanf("%d%d%d",&u,&v,&d);
w[v]=w[v]=d;
path[v]=path[v]=1;
temp[u][v]=temp[v][u]=1;
}

if(BH==YH || BH==M || OF==YH || OF==M)
{
printf("MISSION IMPOSSIBLE.\n");
continue;
}

for(k=1;k<=P;k++)
for(i=1;i<=P;i++)
for(j=1;j<=P;j++)
if(w[i][k]+w[k][j]<w[i][j])
w[i][j]=w[i][k]+w[k][j];

memset(used,0,sizeof(used));
memset(flag,0,sizeof(flag));
flag[0]=1;
flag[P+1]='\0';
used[BH]=1;
flag[BH]=1;
recursion(BH,0,0);
if(flag[YH]==1 || flag[M]==1)
{
printf("MISSION IMPOSSIBLE.\n");
continue;
}
if(YH==M)
{
printf("0\n");
continue;
}
dijkstra(YH);
if(we[M]==9999)
printf("MISSION IMPOSSIBLE.\n");
else
printf("%d\n",we[M]);
}
}

[/c]

bye
rony

[Shantanu]

Don't Worry Rony

Try to catch me,
1. First run a all pair shortest paths.
2. Then find the nodes which are in the shortest path of boss (source to dest)
3. The run a single source shortest path of the employee excluding the
nodes of the boss's shortest path.
4. If exist then print the cost
5. If not then Mission impossible
Thanks

[Subeen]

i am getting WA.

what i tried to do:...

Code: Select all

1. using dijkstra find the shortest path cost from home(yh) to market(m)
2. using dijkstra find all shortest paths from boss's home to office and delete the nodes from the graph.
3. now again using dijkstra find the shortest path cost from home(yh) to market(m).
4. if the cost coputed in step1 is equal to the cost computed in step3 and none of them are infinity then print the cost. else print MISSION IMPOSSIBLE

what i am doing wrong? (or maybe the problem is in my code )
plz help me...

Yes! The Problem was in my Code. The above algorithm is all right

[Subeen]

i am getting WA.

what i tried to do:...

Code: Select all

1. using dijkstra find the shortest path cost from home(yh) to market(m)
2. using dijkstra find all shortest paths from boss's home to office and delete the nodes from the graph.
3. now again using dijkstra find the shortest path cost from home(yh) to market(m).
4. if the cost computed in step1 is equal to the cost computed in step3 and none of them are infinity then print the cost. else print MISSION IMPOSSIBLE

what i am doing wrong? (or maybe the problem is in my code )
plz help me...

[anupam]

modified code in down
any 1 please help me..
thanks...
getting wa again
plz. help

[anupam]

Code: Select all

here is the modified code check it please..
#include<stdio.h>
#define N 110
#define INF 11000
int a[N][N],p[N][N],c[N][N],n,l,m,w[N],b[N][N];
int plus(int a,int b)
{
	if(a==INF || b==INF) return INF;
	return a+b;
}
void ini()
{
	int i,j,k;
	for(i=0;i<n;i++) for(j=0;j<n;j++) b[i][j]=a[i][j];
	for(i=0;i<m;i++) for(j=0;j<w[i];j++) for(k=0;k<n;k++) b[c[i][j]][k]=b[k][c[i][j]]=INF;
}
void fws()
{
	int i,j,k;
	for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++)
		if(plus(a[i][k],a[k][j])<a[i][j])
			a[i][j]=a[i][k]+a[k][j];
}
void init()
{
	int i,j;
	for(i=0;i<n;i++) for(j=0;j<n;j++) a[i][j]=INF,p[i][j]=i;
	for(i=0;i<n;i++) a[i][i]=0;
}
void print(int i,int j)
{
	if(i!=j) print(i,p[i][j]);
	c[m][l++]=j;
}
void fw()
{
	int i,j,k;
	for(i=0;i<n;i++)for(j=0;j<n;j++)	p[i][j]=i,b[i][j]=a[i][j];
	for(i=0;i<m;i++)
		for(j=0;j<w[i]-1;j++)
			b[c[i][j]][c[i][j+1]]=b[c[i][j+1]][c[i][j]]=INF;
	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(plus(b[i][k],b[k][j])<b[i][j])
				{
					b[i][j]=b[i][k]+b[k][j];
					p[i][j]=p[k][j];
				}
}
main()
{
	freopen("in.txt","r",stdin);
	int r,bs,bd,s,d,src,des,val,i,cost;
	while(scanf("%d%d%d%d%d%d",&n,&r,&bs,&bd,&s,&d)!=EOF)
	{
		init();
		for(i=0;i<r;i++)
		{
			scanf("%d%d%d",&src,&des,&val);
			src--;des--;
			if(src!=des) a[src][des]=a[des][src]=val;
		}
		if(s==bs || s==bd || d==bs || d==bd) {printf("MISSION IMPOSSIBLE.\n");continue;}
		if(s==d){printf("0\n");continue;}
		bs--;bd--;fw();
		cost=b[bs][bd];m=0;
		while(1)
		{
			fw();
			if(b[bs][bd]!=cost) break;
			l=0;print(bs,bd);
/*			for(i=0;i<l;i++) printf("%d ",c[m][i]+1);printf("\n");*/
			w[m]=l;m++;
		}
		s--;d--;
		ini();fws();cost=b[s][d];
		if(cost==INF) printf("MISSION IMPOSSIBLE.\n");
		else printf("%d\n",cost);
	}
	return 0;
}

i think this time i havn't missed anything.
please help.