Poj Solution 2834

http://poj.org/problem?id=2834

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> e[10010], dest;
int n, m;
vector< pair<int,int> > jon, cely;

void input( ) {
    int a, b;

    scanf( "%d", &n );
    scanf( "%d", &m );

    while( m-- ) {
        scanf( "%d%d", &a, &b );
        e[a].push_back( b );
        e[b].push_back( a );
    }

    scanf( "%d", &m );
    while( m-- ) {
        scanf( "%d", &a );
        dest.push_back( a );
    }

    scanf( "%d", &m );
    while( m-- ) {
        scanf( "%d%d", &a, &b );
        cely.push_back( make_pair( a, b ) );
    }

}
int dis[10010];

void BFS( ) {
    int i, q[10010], qh = 0, qe = 0, s;

    memset( dis, -1, sizeof dis );

    dis[0] = 0;
    q[qh++] = 0;

    while( qe < qh ) {
        s = q[qe++];
        for( i=0; i<e[s].size(); i++ ) {
            if( dis[e[s][i]] < 0 ) {
                dis[e[s][i]] = dis[s] + 5;
                q[qh++] = e[s][i];
            }
        }
    }
}

void doit( ) {
    int i, j, sum = 0;
    
    BFS( );
    
    jon.push_back( make_pair( 0, 0 ) );
    
    for( i=0; i<dest.size(); i++ ) {
        if( dis[ dest[i] ] > 0 ) {
            jon.push_back( make_pair( dest[i], sum+=dis[dest[i]] ) );
            jon.push_back( make_pair( 0, sum+=dis[dest[i]] ) );
        }
        else {
            jon.push_back( make_pair( dest[i], 1<<31 ) );
            break;
        }
    }

    i=0, j=0;
    for( j=0; j<cely.size(); j++ ) {
        while( i<jon.size() && jon[i].second < cely[j].second )
            i++;
        if( i<jon.size() && jon[i] == cely[j] )
            break;
        if( i == jon.size() && cely[j].first == 0 && cely[j].second >= jon[i-1].second )
            break;
    }

    if( j < cely.size() )
        printf( "%dn", cely[j].second );
    else
        printf( "Being expected..n" );

}

int main( ) {
    input( );
    doit( );
    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *