10354 - Avoiding Your Boss
Moderator: Board moderators
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
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
-
- System administrator & Problemsetter
- Posts: 399
- Joined: Sat Jan 12, 2002 2:00 am
Reply
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
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.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.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- System administrator & Problemsetter
- 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.
MISSION IMPOSSIBLE.
ya...it should be MISSION IMPOSSIBLE.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
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
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.
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
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
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
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
i am getting WA.
what i tried to do:...
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
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
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.
i am getting WA.
what i tried to do:...
what i am doing wrong? (or maybe the problem is in my code )
plz help me...
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
plz help me...
modified code in down
any 1 please help me..
thanks...
getting wa again
plz. help
any 1 please help me..
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"
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;
}
please help.
"Everything should be made simple, but not always simpler"