## 10354 - Avoiding Your Boss

Moderator: Board moderators

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

### 10354 - Avoiding Your Boss

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

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

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

### Mistake

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

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.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Contact: 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,track;
int P,BH,OF,we;
char path,temp,used,flag;

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;
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=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
New poster
Posts: 8
Joined: Sun Oct 20, 2002 6:44 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
Contact:
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 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
Contact:
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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
modified code in down
thanks...
getting wa again
plz. help   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:

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