## 10354 - Avoiding Your Boss

Moderator: Board moderators

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

"you must go outside your home to reach market and your boss must come outside to reach home (from office) or office (from home). "
yes, what you showed, have some logics but i think: there can occur anything what you have mentioned can be or can not be. i mean any two or three or all places of the four terminal places can be the same, though i am not sure. But my two accepted program considered these. you may check judge input and output by submitting as your concepts mentioned by you above.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
noim yet not solved are you a std of BUET ME? leave your Details
Last edited by anupam on Fri Jul 25, 2003 7:29 am, edited 1 time in total.
"Everything should be made simple, but not always simpler"

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

I was wrong. There may have some multiple shortest path in the input of judge input. i solved this problem again with the help of Floyd Warshall method. At firt i got WA for floyd Warshall method. but when i make a consideration of multiple inputs, i got AC using floyd warshell algorithm.

and the terminal position can be all same or some of them are same.

i have to agree , in case of multiple shortest path judge input is not completed enough. But there issss multiple shortest path,in the input.

take care.
__nOi.m....

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

### 10354 -> Incomplete Judge input.

Avoiding the boss ( 10354)

the judge input for this problem is not completed. i have accepted this program thrice. But i have found that my first accepted program gave wrong answer for some input. The inputs and outputs are:

input:
3 3 1 2 3 3
1 2 2
1 3 1
3 2 1
6 6 2 5 3 3
3 2 2
3 5 8
2 5 10
5 1 15
3 4 18
5 4 8
6 6 2 4 1 1
3 5 11
5 1 2
5 4 8
2 5 13
1 4 6
3 4 7
7 7 2 6 4 4
1 3 2
5 3 17
3 6 5
4 6 4
3 4 1
2 3 4
1 2 12
output:
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
i think the input of this program should be completed.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Please tell me the terminal cases again.
I have forget these.
"Everything should be made simple, but not always simpler"

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

your program give the right output for the terminal case input.
i have sent you detail in pm. check it. i have also sent you almost 12 inputs and outputs.

take care.
__nOi.m....

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Could anyone plz give me yet more test cases?

I'm getting WA......

P.S. It's easier to construct the shortest paths with Dijkstra (than Floyd)
Last edited by Observer on Tue Aug 12, 2003 3:07 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Finally got ACC...

I wasted more than an hour because of a silly little mistake in the variable declaration part.... darn...

[EDIT @ July 2006]
Let me add a sample case here:

Code: Select all

``````12 17 6 11 12 9
1 2 1
2 3 1
3 4 1
1 5 1
2 6 1
3 7 1
4 8 1
5 6 1
6 7 1
7 8 1
5 9 1
6 10 1
7 11 1
8 12 1
9 10 1
10 11 1
11 12 1``````
The map looks like this:

Code: Select all

``````x--x--x--x
|  |  |  |
x--BH-x--x
|  |  |  |
M--x--OF-YH``````
Have fun~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

### WA in 10354

Getiing WA in this problem. Here's the code:

Code: Select all

``````#include<stdio.h>
#include<vector>
#include<string.h>

using namespace std;

#define NIL 0
#define MAX 500
#define INF 99999999

typedef struct Node_
{
int id,d;
} Node_;

bool visited[MAX+1];
bool visitedByBoss[MAX+1];
int d[MAX+1],pre[MAX+1];
int v,E,home,office,shop,bossHome;

int findMin();
void markPath(int,int);

void main()
{
int i,u,j;
int m,n,cost;
Node_  next,temp;

while(scanf("%d %d %d %d %d %d",&v,&E,&bossHome,&office,&home,&shop) == 6)
{
for( i = 1; i <= v; i++)
{
d[i] = INF;
}

d[bossHome] = 0;

for( i = 0; i < E; i++)
{
scanf("%d %d %d",&m,&n,&cost);
temp.id = n;temp.d = cost;
}

memset(visited,false,sizeof(visited));
memset(visitedByBoss,false,sizeof(visitedByBoss));
memset(pre,NIL,sizeof(pre));
visitedByBoss[bossHome] = true;

for( i = 0 ; i < v - 1; i++)
{
u = findMin();
visited[u] = true;

for( j = 0; j < adj[u].size(); j++)
{
if(!visited[next.id])
{
if(d[next.id] > d[u] + next.d)
{
d[next.id] = d[u] + next.d;
pre[next.id] = u;
}
}
}
}

markPath(bossHome,office);

if(visitedByBoss[home] || visitedByBoss[shop])
{
puts("MISSION IMPOSSIBLE.");
continue;
}

memset(visited,false,sizeof(visited));
for( i = 1; i <= v; i++) d[i] = INF;
d[home] = 0;

for( i = 0; i < v - 1; i++)
{
u = findMin();
visited[u] = true;

if( !visitedByBoss[u] )
{
for( j = 0; j < adj[u].size(); j++)
{
if( !visited[next.id])
{
if(d[next.id] > d[u] + next.d)
d[next.id] = d[u] + next.d;
}
}
}
}

if(d[shop] >= INF) puts("MISSION IMPOSSIBLE.");
else printf("%d\n",d[shop]);
}
}

int findMin()
{
int i,minIndex,Min = INF;

for( i = 1; i <= v; i++)
{
if( !visited[i])
{
if( d[i] < Min)
{
Min = d[i];
minIndex = i;
}
}
}

return minIndex;
}

void markPath(int s,int t)
{
if( pre[t] == NIL ) return;
else
{
visitedByBoss[t] = true;
markPath(s,pre[t]);
}
}
``````
This code handles the terminal cases(all the req. points are same or some of them are same). But getting WA. Can some1 chk this plz. Or give me some suggestions | | sample I/O.
Shihab
CSE,BUET

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

### What is the problem of my code????

I've posted it somedays ago but now i mean i'm the right way to solve it...
But still i'm getting WA
Plz check my code and give some suggetion.........
I've got all output true for the inputs in the conversation..........
But I got WA actually i mean i cant properly remove the sortest paths of the graph... Plz anyone chake my code.......

Code: Select all

``````#include<stdio.h>

const int inf=1000000;

int w[105][105], d[105][105],b[105][105];
int P, R, BH,YH, OF, M;

void init(){
int i,j;
for (i=1; i<=P; i++){
for (j=1; j<=P; j++)
d[i][j] = w[i][j];
d[i][i] = 0;
}

}

int main()
{
//freopen("10354.out","w",stdout);
int i,j,st,lt,cost,k;
while(scanf("%d%d%d%d%d%d",&P,&R,&BH,&OF,&YH,&M) == 6){

for(i=1; i<=P; i++){
for(j=1; j<=P; j++)
w[i][j] = inf;
}
for(i=0; i<R; i++){
scanf("%d%d%d",&st,&lt,&cost);
if(st != lt){
w[st][lt] = cost;
w[lt][st] = cost;
}
}

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

init();
for(k=1; k<=P; k++){
for(i=1; i<=P; i++){
for(j=1; j<=P; j++){
if(d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];

}
}
}

for(k=1; k<=P; k++){
if(d[BH][k]+d[k][OF]==d[BH][OF]){
for(i=1; i<=P; i++){
w[k][i]=inf;
w[i][k]=inf;
}
}
}

init();
for(k=1; k<=P; k++){
for(i=1; i<=P; i++){
for(j=1; j<=P; j++){
if(d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];

}
}
}

if(d[YH][M] != inf && d[YH][M] != 0)
printf("%d\n",d[YH][M]);
else printf("MISSION IMPOSSIBLE.\n");

}
return 0;
}

``````
Plz help anyone............ I'm worried.....

[/url]
Last edited by rhsumon on Tue Apr 15, 2008 5:04 pm, edited 1 time in total.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Code: Select all

``````int main() {
int i,j,k,r;

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
#endif

while ( scanf("%d %d %d %d %d %d\n",&n,&r,&boss,&office,&me,&market) == 6 ) {
--boss, --office, --me, --market;
memset(g,0xff,sizeof(g));
for ( i = 0 ; i < n; i++ ) g[i][i] = 0;
while ( r-- ) {
scanf("%d %d %d\n",&i,&j,&k);
--i, --j;
if ( i == j ) continue;
assert( g[i][j] == oo );
g[i][j] = g[j][i] = k;
}

if ( boss == me || office == me || market == boss || market == office ) {
IMP;
continue;
}

for ( i = 0; i < n; i++ )
for ( w[i][i] = 0, j = i+1; j < n; j++ )
w[i][j] = w[j][i] = g[i][j];
for ( k = 0; k < n; k++ )
for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ )
if ( w[i][k] < oo && w[k][j] < oo && w[i][j] > w[i][k] + w[k][j] )
w[i][j] = w[i][k] + w[k][j];
for ( i = 0; i < n; i++ )
danger[i] = (w[boss][i] < oo && w[i][office] < oo && w[boss][i] + w[i][office] == w[boss][office]);
danger[boss] = danger[office] = 1;
dijkstra_avoiding_danger_points(me,market);
}
return 0;
}
``````
Verdict: WA.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

safait
New poster
Posts: 4
Joined: Sat Jun 08, 2013 10:49 am

### what is output? for 10354 no problem

i need some input and output for testing my code. problem no is 10354.
and there are some input . i also need output of these input:
12 17 6 11 12 9
1 2 1
2 3 1
3 4 1
1 5 1
2 6 1
3 7 1
4 8 1
5 6 1
6 7 1
7 8 1
5 9 1
6 10 1
7 11 1
8 12 1
9 10 1
10 11 1
11 12 1
3 3 1 2 3 3
1 2 2
1 3 1
3 2 1
6 6 2 5 3 3
3 2 2
3 5 8
2 5 10
5 1 15
3 4 18
5 4 8
6 6 2 4 1 1
3 5 11
5 1 2
5 4 8
2 5 13
1 4 6
3 4 7
7 7 2 6 4 4
1 3 2
5 3 17
3 6 5
4 6 4
3 4 1
2 3 4
1 2 12

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: what is output? for 10354 no problem

7
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
Check input and AC output for thousands of problems on uDebug!

Aarya
New poster
Posts: 8
Joined: Thu Nov 21, 2013 6:05 pm

### Re: 10354 - Avoiding Your Boss

Your boss must not see you outside your home. You can assume that the cost of reaching another location in the same place is zero and you must go outside your home to reach market and your boss must come outside to reach home (from office) or office (from home)
If I understood this statement correctly then
for these input:
2 1 3 3 3 3
1 2 1

2 2 3 3 3 3
1 2 1
2 3 2

output should be:
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
rather than:
0
0
Aren't they?
But when I ran my friend's accepted code against this it produced:
0
0

Thanks.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10354 - Avoiding Your Boss

P = Total number of places. (0<P<=100)
R = Total number of connecting roads. (0<=R<=4950)
BH = The Place where your boss lives. (0<BH<=P)
OF = The place where your office is situated. (0<OF<=P)
YH = The place where your home is situated. (0<YH<=P)
M = The place where the market is situated. (0<M<=P)
Check input and AC output for thousands of problems on uDebug!