[UVa] 10342 - Always Late

題意:
(from luckycat)


解法:
可以用 SPFA 再變形來解。

注意:

程式碼:

	/**
	* 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;
	}

view raw 10342 - Always Late.cpp hosted with ❤ by GitHub