11463  Commandos
Moderator: Board moderators
11463  Commandos
Hi,
i have no idea about this problem,
can anyone else help me?
i have no idea about this problem,
can anyone else help me?

 Experienced poster
 Posts: 196
 Joined: Wed May 02, 2007 10:12 pm
 Location: Hungary, Pest county, Halasztelek
 Contact:
Re: 11463  Commandos
Use FloydWarshall in O(V^3), or two bfs in O(E) time.
Re: 11463  Commandos
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 FloydWarshall or other algorithms for this problem, can you show me for details.
thanks a lot.
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 FloydWarshall or other algorithms for this problem, can you show me for details.
thanks a lot.
Re: 11463  Commandos
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
If there is N buildings, think about using N commandos (one command for one building).

Rio
Re: 11463  Commandos
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.
when i draw the graph in paper and finally realize it can simply reduce to a very simple formula.
thx a lot.
Re: 11463  Commandos
Hi, I am getting W.A in this problem.
Someone please help.
Thanks in advance to all.
Someone please help.
Code: Select all
Removed after AC.
Last edited by mukit on Wed Sep 10, 2008 12:03 pm, edited 1 time in total.
Re: 11463  Commandos
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]+dist[dest] ) for all i.
Hope this helps.
The actual answer is MAX(dist[root]+dist[dest] ) for all i.
Hope this helps.
Re: 11463  Commandos
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.
and then sum them.
However thanks a lot to Shamim vi. I got AC now.
Re: 11463  Commandos
hi all,
i am litle confused how to use FloydWarshall's algorithm in this problem.
i searched for that algorithm & i found this general code
can someone help plz
i am litle confused how to use FloydWarshall'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[k1][i][j], dist[k1][i][k] + dist[k1][k][j])
Re: 11463  Commandos
You can find the all pair shortest path with FloydWarshall algorithm..
After that, you should do something more..
See shamim's post
After that, you should do something more..
See shamim's post
Re: 11463  Commandos
thx a lot helloneo
i figured it out but, unfortunately i got WA :S
here is my code
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==N1)
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;
}
Re: 11463  Commandos
I used two bfs.
Tested input output.Still WA.
Can anyone give some critical input output?
output:
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
Code: Select all
Case 1: 4
Case 2: 1
Case 3: 4

 Learning poster
 Posts: 97
 Joined: Fri Aug 22, 2008 10:18 pm
 Location: CSE.SUST.SYLHET
Re: 11463  Commandos
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.......
Last edited by saiful_sust on Sat Sep 12, 2009 12:35 pm, edited 1 time in total.

 Learning poster
 Posts: 97
 Joined: Fri Aug 22, 2008 10:18 pm
 Location: CSE.SUST.SYLHET
Re: 11463  Commandos
Some one PLZ help me .........

 Learning poster
 Posts: 97
 Joined: Fri Aug 22, 2008 10:18 pm
 Location: CSE.SUST.SYLHET
Re: 11463  Commandos
Its boring no body help me
PLZ some one help me