UVa-383, Live Archive-5430, TJU-1572, POJ-1529, ZOJ-1285 : Shipping Routes

問題概要

ノード数V(<30)のグラフで全点間最短路を求める問題。

解法

Warshall-Floyd。入出力が面倒。オンラインジャッジごとに必要なスペースの数が違う。

acceptされたコード

計算量O(V^3)。

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

const int MAX_N = 30;
const int INF = 1<<29;

map<string, int> get_id;
char buf1[30], buf2[30];
int N, M, Q;
int graph[MAX_N][MAX_N];


void init(){
	scanf("%d%d%d ", &N, &M, &Q);
	get_id.clear();

	for(int i=0; i<N; i++){
		scanf(" %s ", buf1);
		get_id[string(buf1)] = i;
	}

	for(int i=0; i<N; i++){
		fill(graph[i], graph[i] + N, INF);
	}

	for(int i=0; i<M; i++){
		scanf(" %s %s ", buf1, buf2);
		graph[get_id[string(buf1)]][get_id[string(buf2)]] = graph[get_id[string(buf2)]][get_id[string(buf1)]] = 1;
	}
}

void solve(){
	for(int k=0; k<N; k++){
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}

	for(int i=0; i<Q; i++){
		int d, len;
		scanf(" %d %s %s ", &d, buf1, buf2);
		len = graph[get_id[string(buf1)]][get_id[string(buf2)]];
		if(len == INF){
			puts("NO SHIPMENT POSSIBLE");
		}
		else{
			printf("$%d\n", d*len*100);
		}
	}
}

int main(){
	int T;
	scanf("%d",&T);
	puts("SHIPPING ROUTES OUTPUT\n");
	for(int c=1; c<=T; c++){
		printf("DATA SET  %d\n\n", c);
		init();
		solve();
		puts("");
	}

	puts("END OF OUTPUT");

	return 0;
}