RUPC C, AOJ-2283: Seishun 18 Kippu

その他のコンテスト AOJ

問題概要

頂点数N(<500)、辺数M(<5000)の無向グラフが与えられる。A->B->Cという経路の最短路を求める問題。

考えたこと

  • どう見てもただの最短路。途中によるとかはdist(A,B) + dist(B,C)を答えるだけでよい。
  • 入力がやたら面倒くさい。頂点は文字列で与えられるしコストはx/40+yという辺な形になってるし…。
    • 個人的には、はじめから入力はindex1, index2, costで与えてほしいと思った。
    • この問題をそのまま出したら簡単過ぎるというのは理解できる。
    • 複雑化が悪いとは言わないけど、こういうのは面倒さしか強調されないので…。
  • N=500なのでWarshall-Floydで解いた。
    • Warshall-FloydのO(N^3)は係数1だから割と信頼できて、しかもループの順序がメモリの局所化にやさしいので実際はそれなりに高速に動作する(N=1000とかでも1秒切ったりとか)。
  • わりとすぐに書けた。予想通り余裕を持った実行時間でAC。

本番中通ったコード

計算量O(N^3)。

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

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

int N, M;
int graph[MAX_N][MAX_N];
const int start = 0, mid = 1, goal = 2;

int 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]);
			}
		}
	}

	return graph[start][mid] + graph[mid][goal];
}

int main(){

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

		int cnt = 0;
		map<string, int> dict;
		string st, md, gl;
		cin.ignore();
		cin >> st >> md >> gl;

		dict[st] = cnt++;
		dict[md] = cnt++;
		dict[gl] = cnt++;

		for(int i=0; i<M; i++){
			cin.ignore();
			string from, to;
			int x, y;
			cin >> from >> to >> x >> y;
			if(dict.find(from) == dict.end()){
				dict[from] = cnt++;
			}
			if(dict.find(to) == dict.end()){
				dict[to] = cnt++;
			}

			graph[dict[from]][dict[to]] = min(graph[dict[from]][dict[to]], x/40 + y);
			graph[dict[to]][dict[from]] = graph[dict[from]][dict[to]];
		}

		printf("%d\n", solve());
	}

	return 0;
}