10354 - Avoiding Your Boss

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

Moderator: Board moderators

amitc
New poster
Posts: 3
Joined: Fri Sep 13, 2002 6:02 pm

10354 - Avoiding Your Boss

Post by amitc » Wed Sep 18, 2002 3:51 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Reply

Post by shahriar_manzoor » Wed Sep 18, 2002 4:30 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Sep 18, 2002 4:39 pm

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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Wed Sep 18, 2002 6:36 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Sep 18, 2002 6:45 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Mistake

Post by shahriar_manzoor » Thu Sep 19, 2002 2:10 am

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

MISSION IMPOSSIBLE.

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Thu Sep 19, 2002 4:01 am

Even wrote: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 :o

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
New poster
Posts: 3
Joined: Fri Sep 13, 2002 6:02 pm

thanks to all

Post by amitc » Thu Sep 19, 2002 7:23 am

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Sep 19, 2002 2:41 pm

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
New poster
Posts: 5
Joined: Sat Oct 19, 2002 4:20 am
Location: Dhaka,Bangladesh
Contact:

Post by minhaz » Fri Nov 08, 2002 6:45 am

:roll:

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

:o
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 :oops:

Shantanu
New poster
Posts: 8
Joined: Sun Oct 20, 2002 6:44 am

Post by Shantanu » Sun Dec 15, 2002 8:26 am

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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Fri Apr 04, 2003 5:00 pm

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... :oops:

Yes! The Problem was in my Code. The above algorithm is all right :D
Last edited by Subeen on Tue Aug 12, 2003 10:57 am, edited 1 time in total.

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Fri Apr 04, 2003 5:01 pm

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... :oops:

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sun May 18, 2003 5:32 am

modified code in down
any 1 please help me..
thanks...
getting wa again
plz. help
:oops: :oops: :oops:
Last edited by anupam on Tue Jul 22, 2003 5:09 pm, edited 2 times in total.
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Jun 06, 2003 11:43 am

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. :oops: :oops: :oops:
"Everything should be made simple, but not always simpler"

Post Reply

Return to “Volume 103 (10300-10399)”