11463 - Commandos

[wahaha]

Hi,

i have no idea about this problem,

can anyone else help me?

[Robert Gerbicz]

Use Floyd-Warshall in O(|V|^3), or two bfs in O(|E|) time.

[wahaha]

for the sample
4
3
0 1
2 1
1 3
0 3

it seems i am confused about the problem

i know there needs two commandos and the path is

0->1->3 which needs two units time
0->1->2->1->3 which needs four units time

i think there are so many status and i can only think the searching algorithm, but it seems too slow.

i can not implement Floyd-Warshall or other algorithms for this problem, can you show me for details.

thanks a lot.

[rio]

There is no restriction in how many commandos you use.
If there is N buildings, think about using N commandos (one command for one building).

-----
Rio

[wahaha]

i got it and ac finally.

when i draw the graph in paper and finally realize it can simply reduce to a very simple formula.

thx a lot.

[mukit]

Hi, I am getting W.A in this problem.
Someone please help.

Code: Select all


Removed after AC.



Thanks in advance to all.

[shamim]

Mukit, your approach is correct, but it is not clear what you were trying to do after finding the all pair shortest path.

The actual answer is MAX(dist[root][i]+dist[i][dest] ) for all i.

Hope this helps.

[mukit]

My approach was first finding the most distant node and then calculating the distance of this from the meeting node
and then sum them.
However thanks a lot to Shamim vi. I got AC now.

[sohanasr]

hi all,
i am litle confused how to use Floyd-Warshall's algorithm in this problem.
i searched for that algorithm & i found this general code
can someone help plz

Code: Select all

for i = 1 to N
   for j = 1 to N
      if there is an edge from i to j
         dist[0][i][j] = the length of the edge from i to j
      else
         dist[0][i][j] = INFINITY
 
for k = 1 to N
   for i = 1 to N
      for j = 1 to N
         dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])

[helloneo]

You can find the all pair shortest path with Floyd-Warshall algorithm..
After that, you should do something more..

See shamim's post

[sohanasr]

thx a lot helloneo
i figured it out but, unfortunately i got WA :S
here is my code

Code: Select all

#include<iostream>
using namespace std;
int dist[2][100][100]={0};bool Array1[100][100];int N,root,dest;

void Commandos (int x,int counter,int a)
{
   int q=0;
   for (int i=0;i<N;i++)
   {
      if (i==x)
         continue;
      if (Array1[x][i]==true && Array1[i][x]==true && dist[a][x][i]==0)
      {
         Array1[x][i]=false;counter++;
         if (a==1)
            dist[a][dest][i]=counter;
         else
            dist[a][root][i]=counter;
         Commandos(i,counter,a);
         counter--;
      }
      else
         q++;
   }
   if (q==N-1)
      return;
}
int main()
{
   int count=0,counter=0,T,R;
   scanf("%d",&T);
   for (int z=0;z<T;z++)
   {
      counter=0;count++;bool Array[100][100]={false};
      scanf("%d\n%d",&N,&R);
      for (int y=0;y<R;y++)
      {
         scanf("%d %d",&root,&dest);
         Array[root][dest]=true;
         Array[dest][root]=true;
      }
      scanf("%d\n%d",&root,&dest);
      for (int i=0;i<N;i++)
         for (int j=0;j<N;j++)
            Array1[i][j]=Array[i][j];
      Commandos(dest,0,1);
      for (int i=0;i<N;i++)
         for (int j=0;j<N;j++)
            Array1[i][j]=Array[i][j];
      Commandos(root,0,0);
      for (int i=0;i<N;i++)
         if (counter<dist[0][root][i]+ dist[1][dest][i])
               counter=dist[0][root][i]+ dist[1][dest][i];
      printf("Case %d: %d\n",count,counter);
      for (int i=0;i<N;i++)
         for (int j=0;j<N;j++)
         {
            dist[0][i][j]=0;
            dist[1][i][j]=0;
         }

   }
   return 0;
}

[lnr]

I used two bfs.
Tested input output.Still WA.
Can anyone give some critical input output?

Code: Select all

3
4
3
0 1
2 1
1 3
0 3
2
1
0 1
1 0
4
3
0 1
2 1
1 3
0 0


output:

Code: Select all

Case 1: 4
Case 2: 1
Case 3: 4


[saiful_sust]

Hi I try to solve this problem

But i get wa...........
I use two BFS...
Here is my code..............
PLZ help me..........

Code: Select all

Cut after ACC.......


[saiful_sust]

Some one PLZ help me .........

[saiful_sust]

Its boring no body help me

PLZ some one help me