11463 - Commandos

[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

Code: Select all

Case 1: 4

ur output is

Code: Select all

Case 1: 5

pls explain ur process,its quite simple warshall application,

[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

[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;
}

[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