11463 - Commandos

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11463 - Commandos

Post by Jehad Uddin » Wed Sep 09, 2009 4:27 pm

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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11463 - Commandos

Post by saiful_sust » Sat Sep 12, 2009 12:39 pm

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
:D :D

rahid
New poster
Posts: 9
Joined: Tue Oct 13, 2009 7:13 am
Location: Asian University of Bangladesh
Contact:

Re: 11463 - Commandos

Post by rahid » Thu Jul 14, 2011 12:11 am

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
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 11463 - Commandos

Post by prashantharshi » Sat Jun 14, 2014 6:49 am

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

Post Reply

Return to “Volume 114 (11400-11499)”