[UVa] 10048 - Audiophobia

題目網址: http://goo.gl/yxVJb6

題意:在一無向圖中，有 c 座城市、 s 條街道、 q 個詢問， s 條街道的起點終點與噪音值，q 個詢問中，每個詢問會包含兩個城市 A、B，問從 A 走到 B 的路徑中，所需 "忍受" 的最小噪音值。



解法: 想法跟最短路徑有點像，且會詢問任兩點的最小的路徑間最大噪音，所以想到 Floyd Warshall。

關鍵 pseudocode
FOR( k, 1, c ) FOR( i, 1, c ) FOR( j, 1, c )
    edge[i][j] = min( edge[i][j], min( edge[i][k], edge[k][j] ) );

TAG: Floyd Warshall

注意:

程式碼:

	/**
	* Tittle: 10048 - Audiophobia
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/09
	* File: 10048 - Audiophobia.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	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 C 105
	#define S 1005
	#define Q 10005
	#define INF 1e9
	// declarations
	int t=1;
	int c, s, q;
	int edge[C][C];
	// functions
	void floyd_warshall( void )
	{
	FOR( k, 1, c ) FOR( i, 1, c ) FOR( j, 1, c ) {
	if( edge[i][k]==-1 || edge[k][j]==-1 ) continue;
	if( i==j || j==k || k==i ) continue;
	if( edge[i][j] == -1 ) edge[i][j] = INF;
	edge[i][j] = min( edge[i][j], max(edge[i][k],edge[k][j]) );
	}
	}
	// main function
	int main( void )
	{
	int u, v, d;
	// input
	while( scanf( "%d%d%d", &c, &s, &q )==3 && (c||s||q) ) {
	clr( edge, -1 );
	FOR( i, 1, s ) {
	scanf( "%d%d%d", &u, &v, &d );
	edge[u][v] = edge[v][u] = d;
	}
	// solve
	floyd_warshall();
	// output
	if( t > 1 ) putchar('\n');
	printf( "Case #%d\n", t++ );
	FOR( i, 1, q ) {
	scanf( "%d%d", &u, &v );
	if( edge[u][v] == -1 ) puts("no path");
	else printf( "%d\n", edge[u][v] );
	}
	}
	return 0;
	}

view raw 10048 - Audiophobia.cpp hosted with ❤ by GitHub