OJ Board

Code: Select all

#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;

int N, R;
map < string, int > ind;
int adj[200][200] = { false };

void floyd_warshall() {
	for( int k = 0; k < N; ++k )
		for( int j = 0; j < N; ++j )
			for( int i = 0; i < N; ++i )
				if( adj[i][k] != 0 && adj[k][j] != 0 ) {
					adj[i][j] >?= min( adj[i][k], adj[k][j] );
					//adj[i][j] = adj[j][i] = min( adj[i][j], adj[j][i] );
				}
}

int main() {
	int cnt = 1;
	
	scanf( "%d %d", &N, &R );
	while( !( N == 0 && R == 0 ) ) {
		int w, n = 0; 
		string s1, s2;
		
		memset( adj, 0, sizeof( adj ) );
		ind.clear();
 		for( int i = 0; i < R; ++i ) {
			cin >> s1 >> s2 >> w;
			
			if( ind.count(s1) == 0 ) ind[s1] = n++;
			if( ind.count(s2) == 0 ) ind[s2] = n++;
		
			adj[ind[s1]][ind[s2]] = adj[ind[s2]][ind[s1]] = w;
		}
		
		floyd_warshall();
		cin >> s1 >> s2;
		
		cout << "Scenario #" << cnt++ << endl;
		cout << adj[ind[s1]][ind[s2]] << " tons" << endl << endl;
				
		scanf( "%d %d", &N, &R );
	}
	
	return 0;
}

Code: Select all

               adj[i][j] >?= min( adj[i][k], adj[k][j] ); 

Code: Select all

               adj[i][j] >?= min( adj[i][k], adj[k][j] );