Page **2** of **2**

### Re: 11463 - Commandos

Posted: **Wed Sep 09, 2009 4:27 pm**

by **Jehad Uddin**

try this case,

Code: Select all

```
1
6
8
0 1
0 2
1 2
1 3
3 5
3 4
2 3
4 5
0 5
```

correct output

ur output is

pls explain ur process,its quite simple warshall application,

### Re: 11463 - Commandos

Posted: **Sat Sep 12, 2009 12:39 pm**

by **saiful_sust**

Thanks Jehad Uddin 4 ur test case

I solve in two ways

1. with two BFS( one 4 finding the max depth and another for reaching the destination from final state)

2. easy warshall

### Re: 11463 - Commandos

Posted: **Thu Jul 14, 2011 12:11 am**

by **rahid**

Please help me. I'm unable to solve it.

Code: Select all

```
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
#define IN ({int _T; scanf("%d", &_T); _T;})
#define REP(i, limit) for(int i = 0; i < limit; i++)
#define CLEAR(a) memset(a, '\0', sizeof(a))
#define FR freopen("in.txt", "r", stdin)
#define FW freopen("out.txt", "w", stdout)
#define INF (1<<30)
const double PI=acos(-1.0);
const double EPS=1e-11;
int main() {
//FR;
int T, N, R, u, v, s, d, cas = 0;
int road[100][100];
T = IN;
while(T--) {
int cnt = 0;
bool visited[100] = {false};
N = IN; R = IN;
REP(i, N)
REP(j, N) {
if(i == j) road[i][j] = 0;
else road[i][j] = INF;
}
REP(i, R) {
u = IN; v = IN;
road[u][v] = road[v][u] = 1;
}
queue<int> q;
s = IN; d = IN;
q.push(s);
while(!q.empty()) {
int t = q.front();
q.pop();
visited[t] = true;
REP(i, N) {
if(road[t][i] == 1) {
if(!visited[i]) q.push(i);
road[s][i] = min(road[s][i], road[s][t] + road[t][i]);
}
//cout << road[s][d] << " ";
}
}
printf("%d\n", road[s][d]);
}
return 0;
}
```

### Re: 11463 - Commandos

Posted: **Sat Jun 14, 2014 6:49 am**

by **prashantharshi**

here u have to travel all the vertices

but in bfs tree where there a branching occurs then return the max depth incurred bcoz by that tym other fleet would have completed the other branch

so u just find the max(dist[root]*+dist**[s]) after floyd warshall*