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.