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 Floyd-Warshall 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 Floyd-Warshall 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 Floyd-Warshall 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 Floyd-Warshall'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 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])
Re: 11463 - Commandos
You can find the all pair shortest path with Floyd-Warshall 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==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;
}
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![]()
![]()
![]()