Page 2 of 4

Posted: Wed Jun 11, 2003 6:32 pm
by 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.

Posted: Thu Jun 12, 2003 9:40 am
by anupam
:oops: :oops: :oops: missing your words.
will you be a little bit clear?
wanting help from all of you.
--
:oops: :oops: [/b]

Posted: Thu Jun 12, 2003 7:47 pm
by 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.

Posted: Sat Jun 14, 2003 1:31 pm
by 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.

Posted: Sat Jun 14, 2003 6:36 pm
by 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. :)

Posted: Sun Jun 15, 2003 2:14 pm
by 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.
---
:oops: :oops:

Posted: Sun Jun 15, 2003 3:51 pm
by 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]

Posted: Tue Jul 22, 2003 10:08 am
by Observer
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??

Posted: Tue Jul 22, 2003 10:22 am
by 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).

Posted: Tue Jul 22, 2003 10:27 am
by Observer
Then I'll just have to use Dijkstra for this part... :D

Thx! I'll try it.

Posted: Tue Jul 22, 2003 12:19 pm
by Noim
yes observer,

i have used Disktra' Algorithm too. :D

Posted: Tue Jul 22, 2003 5:07 pm
by 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 :oops: :oops: [/b]

Posted: Tue Jul 22, 2003 11:16 pm
by 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.

Posted: Wed Jul 23, 2003 12:50 am
by 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.

Posted: Wed Jul 23, 2003 3:12 am
by 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!