10342 - Always Late

10342 - Always Late.cpp

/**
 * Tittle:	10342 - Always Late
 * Author:	Cheng-Shih, Wong
 * Date:	2015/07/04
 */

// include files
#include <bits/stdc++.h>

using namespace std;

// definitions
#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
#define clr(x,v) memset( x, v, sizeof(x) )
#define INF 1e7
#define N 105

struct Edge {
	int v, d;

	Edge( int _v, int _d ):
		v(_v), d(_d) {}
};

typedef queue<int> QI;
typedef vector<Edge> VE;

// declarations
int n, m;
int ti = 1;
int d[N][2];
int inQ[N];
VE edge[N];

// functions
void init( void )
{
	FOR( i, 0, n-1 ) edge[i].clear();
	
	int u, v, dis;
	FOR( i, 1, m ) {
		scanf( "%d%d%d", &u, &v, &dis );
		edge[u].push_back( Edge(v,dis) );
		edge[v].push_back( Edge(u,dis) );
	}
}

void spfa( int s, int t )
{
	QI que;
	int u, newdis, v;
	clr( inQ, false );
	FOR( i, 0, 100 ) d[i][0] = d[i][1] = INF;
	d[s][0] = 0;
	que.push( s );
	inQ[s] = true;

	while( !que.empty() ) {
		u = que.front();
		que.pop();
		inQ[u] = false;

		for( auto eg : edge[u] ) {
			v = eg.v;

			newdis = eg.d+d[u][0];
			if( newdis!=d[v][0] && newdis!=d[v][1] ) {
				if( newdis < d[v][1] ) {
					d[v][1] = newdis;
					
					if( d[v][1] < d[v][0] )
						swap( d[v][1], d[v][0] );

					if( !inQ[v] ) {
						inQ[v] = true;
						que.push(v);
					}
				}
			}

			newdis = eg.d+d[u][1];
			if( newdis!=d[v][0] && newdis!=d[v][1] ) {
				if( newdis < d[v][1] ) {
					d[v][1] = newdis;
					
					if( d[v][1] < d[v][0] )
						swap( d[v][1], d[v][0] );

					if( !inQ[v] ) {
						inQ[v] = true;
						que.push(v);
					}
				}
			}
		}
	}

	if( d[t][1] == INF ) puts("?");
	else printf( "%d\n", d[t][1] );
}

void solve( void )
{
	int k, u, v;

	scanf( "%d", &k );

	while( k-- ) {
		scanf( "%d%d", &u, &v );
		spfa( u, v );
	}
}

// main function
int main( void )
{
	
	// input
	while( scanf( "%d%d", &n, &m )==2 ) {
		init();
		printf( "Set #%d\n", ti++ );
		solve();
	}
	
	return 0;
}