## 10354 - Avoiding Your Boss

Moderator: Board moderators

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
if marcket and your home is in a same place , your output is zero .
but is that value zero all the time?
Though you have considered some cases, you have missed another.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
will you be a little bit clear?
wanting help from all of you.
--
[/b]
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am

if(s==d){printf("0\n");continue;}
here you don't consider further more check.
it is not always 0 for all input. you need futher check.

I have just found this bug on your code. Besides this , your code seems right to me. I can't say if there were any bugs.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
as i have to avoid the nodes in the shortest path.
if boss doesn't come s & d places so what cost there may be?
--
may be my problem was little like a fool. but i have no idea yet.
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
if(s==d){printf("0\n");continue;}
Here you have broken for processing further more.
as i have to avoid the nodes in the shortest path.
if boss doesn't come s & d places so what cost there may be?

yes you have to avoid the nodes in the shortest path of your boss.
But you have not consider boss's path if s==d. Why are you thinking if your_home==marcket && (office!=your_marcket || boss_home!=marcket) , then boss won't visit the marcket or your_home.

if i am not still clear, please tell me. i will try to give some sample input here.

i wish now you could solve this problem.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i think i have got it.
but i will be happier if you give a sample input and corresponding output.
--
---
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
hi,

Sample input:
3 3 1 2 3 3
1 2 8
1 3 4
2 3 3
I think this will clear you what i want to say.

wish you good luck.

[/list]
__nOi.m....

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Shantanu wrote:2. Then find the nodes which are in the shortest path of boss (source to dest)
I don't understand...

Would there be more than ONE shortest path form the office and your boss' home?? If so, how can we do step 2 (quoted above) efficiently?

By DFS? DP??
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
hi observer,

i have got AC 2 times for this problem.
first i got AC considering only one shortest path from boss home to office.
then considering multiple shortest path.

as i got AC for both consideration independently, i think there is no inputs of multiple shortest path from boss home to offce.

Again, the interesting matter is that: the problem setter told the output of the intput given by Even (in page 1) is MISSION IMPOSSILBE. But if any program outputs "30" for that input, it would get AC. (i don't know if there declared any rejudgement for this problems or not).
__nOi.m....

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Then I'll just have to use Dijkstra for this part...

Thx! I'll try it.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
yes observer,

i have used Disktra' Algorithm too.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
hello noim, and even,
so why getting wa noe.
i think i figured out your test test cases perfectly..
here is the modified code..

Code: Select all

``````#include<stdio.h>
#define INF 10000
#define N 10
int a[N][N],p[N][N],c[N],l,n,b[N][N];
int plus(int a,int b)
{
if(a==INF || b==INF) return INF;
return a+b;
}
void fw()
{
int i,j,k;
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];
}
}
void print(int i,int j)
{
if(i!=j) print(i,p[i][j]);
c[l++]=j;
}
main()
{
int m,bs,bd,s,d,i,j,in,inn,cost;
while(scanf("%d%d%d%d%d%d",&n,&m,&bs,&bd,&s,&d)!=EOF)
{
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;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&in,&inn,&cost);
if(in!=inn) a[in-1][inn-1]=a[inn-1][in-1]=cost;
}
while(1)
{
for(i=0;i<n;i++) for(j=0;j<n;j++) b[i][j]=a[i][j],p[i][j]=i;;
fw();
if(b[bs-1][bd-1]==INF) break;
l=0;
print(bs-1,bd-1);
for(i=0;i<l;i++)
{
for(j=0;j<n;j++) a[c[i]][j]=INF;
}
}
if(a[s-1][d-1]==INF || s==bs || s==bd || d==bs || d==bd) printf("MISSION IMPOSSIBLE.\n");
else if(s==d)
{
printf("0\n");
}
else			printf("%d\n",a[s-1][d-1]);
}
return 0;
}
``````
plz help.
not getting ac for many dayz [/b]
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Anupum vai,

there is a sample input below. may be this is only input you didn't consider.

Inputs:
5 5 1 2 3 4
1 2 1
1 5 10
5 2 10
3 5 1
5 4 1
outputs:
2
if you again got WA, please inform me.
__nOi.m....

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Anupum vai,

you asigned the value of N as only 10.
but the value can be maximum 100.

your program even does not work for the input:

input:
9 5 1 2 3 4
3 5 1
5 6 1
6 7 1
7 8 1
8 4 1
output:
5
may be this is because of you used variable a[][] instead of b[][]. (may be absent mindly)
else printf("%d\n",a[s-1][d-1]);

it may be b[s-1][d-1]

&& also:
if(a[s-1][d-1]==INF || s==bs || s==bd || d==bs || d==bd) printf("MISSION IMPOSSIBLE.\n");

it may also be if(b[s-1][d-1]==INF....

you have calculated shortest path using b[][], and a[][] is used to cut the boss's path and copying to b[][] before using floyed-warshall algorithm on b[][] matrix. so b[][] contain the shortest path distance at the last of the program.
please don't mind if my explanation is wrong.

you have to consider another case:

if there is office on the shortest way to marcket from the home even office can not be reached from the boss home.
__nOi.m....

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Excuse me...

According to the problem description:
"you must go outside your home to reach market and your boss must come outside to reach home (from office) or office (from home). "
and
Does that mean that
1. Your home and the market are NOT at the same place;
2. The boss' home and the office are also NOT on the same spot;
3. Your home and the office are NOT on the same spot;
4. And your home and boss' home are NOT at the same place?

Then can
1. the market and the office be on the same spot;
2. the market and boss' home be on the same spot?

7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org