AOJ-1169: The Most Powerful Spell (最強の呪文)

keyword

問題概要

ノード数N(<40)、エッジ数A(<400)以下の重み付き(重みは文字列)有向グラフが与えられるのである2点間の辞書順最小の重み和(後方に付け加えていく)が定まるならばそれを出力する問題。

解法

後ろからベルマンフォードとか1文字ずつ分解とかいろいろ頭の良い解法があるのは知っているけど適当に前処理をかけた後普通にDijkstraっぽく解いてみた。ただしDijkstraをそのまま適用するのはダメだとすぐにわかるのでちょっと工夫する。普通のDijkstraは始点からの最小重みを配列に持っておくけど、この場合は最小のprefixになりうるものを全て持っておく。つまり、文字列A,Bのどちらかがもう一方のprefixであるときにはこの2つの間に順序を定めない。Dijkstraと異なり始点からの最小重みでなく(その時点での)極小重みを全て持っておくことにする。閉路の検出は文字列の長さが(最大の文字列の長さ=6)*Nをこえた時点で判断できる(鳩ノ巣原理)。

感想

もう少し枝刈りできそうだけどとりあえず投げてみるかー、って投げてみたらそれなりの速度で通った。

#include <cstdio>
#include <set>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>

using namespace std;

typedef pair<string, int> state;
const int MAX_N = 42;
int N, start, goal;
bool G[MAX_N][MAX_N];
vector<string> ws[MAX_N][MAX_N];
set<string> dist[MAX_N][MAX_N];

inline bool strictLarge(string a, string b){
	int len = min(a.length(), b.length());
	for(int i=0; i<len; i++){
		if(a[i] != b[i]) return a[i]>b[i];
	}
	return false;
}

void init(){
	for(int k=0; k<N; k++){
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				G[i][j] |= (G[i][k] && G[k][j]);
			}
		}
	}
	for(int i=0; i<N; i++)if(!G[i][goal] && i!=goal){
		for(int j=0; j<N; j++){
			G[j][i] = false;
		}
	}
}

string solve(){
	init();
	if(!G[start][goal]){
		return "NO";
	}
	priority_queue< state, vector<state>, greater<state> > Q;
	vector< set<string> > dist(N);

	Q.push( make_pair("", start) );
	dist[start].insert("");

	while(!Q.empty()){
		state tp = Q.top(); Q.pop();
		string str = tp.first;
		if(str.length() > 6*N){
			return "NO";
		}
		int cur = tp.second;
		if(cur == goal){
			return str;
		}
		if(strictLarge(str, *dist[cur].rbegin())){
			continue;
		}
		for(int i=0; i<N; i++)if(G[i][goal] || i==goal){
			for(int j=0; j<(int)ws[cur][i].size(); j++){
				string wd = str + ws[cur][i][j];
				if(dist[i].find(wd) == dist[i].end()){
					dist[i].insert(wd);
					Q.push( make_pair(wd, i) );
				}
			}
		}
	}
	return "ERROR";
}

int main(){
	int A;
	while(scanf("%d%d%d%d",&N,&A,&start,&goal), N){
		for(int i=0; i<N; i++)for(int j=0; j<N; j++) G[i][j] = false;
		for(int i=0; i<N; i++)for(int j=0; j<N; j++) ws[i][j].clear();
		for(int i=0; i<A; i++){
			char buf[10];
			int x, y;
			scanf("%d%d %s ", &x, &y, buf);
			G[x][y] = true;
			ws[x][y].push_back(string(buf));
		}
		puts(solve().c_str());
	}
	return 0;
}