10354 - Avoiding Your Boss

[Noim]

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.

[anupam]

missing your words.
will you be a little bit clear?
wanting help from all of you.
--
[/b]

[Noim]

your uses in your code :

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.

[anupam]

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.

[Noim]

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.

[anupam]

i think i have got it.
but i will be happier if you give a sample input and corresponding output.
--
thanks for your great help.
---

[Noim]

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]

[Observer]

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

[Noim]

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

[Observer]

Then I'll just have to use Dijkstra for this part...

Thx! I'll try it.

[Noim]

yes observer,

i have used Disktra' Algorithm too.

[anupam]

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]

[Noim]

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.

[Noim]

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.

[Observer]

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

"Your boss must not see you outside your home."

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?

Thx for your attention!