2010 ICPC国内予選 E.最強の呪文

問題概要

辺に英小文字からなる呪文が書かれた有向グラフがある。
スタートからゴールまでグラフを辿ったときに得られる、「それまでにたどった辺の呪文を並べた」文字列のうち、辞書順で最も先頭に来るものを最強の呪文と呼ぶ。

最強の呪文が一意に決まる場合それを、決まらない場合"NO"を出力せよ。

（あ、なんか要約が適当……）

解法

長さが一定なら、呪文の強さは一意に定まる。

したがって、それぞれのノードにたどり着いた時点で、長さがL（0≦L≦500くらいまで）の最強の呪文を全て覚えながらダイクストラ法。
呪文の長さが長かったらループしているので、500字くらいで適当に打ち切ってよい。

そもそもゴールにたどり着けない場合および、ゴールに着いた時の呪文が長すぎる場合は、最強の呪文が決定できないときなので"NO"を出力する。

ソースコード

AOJで1.3secくらいでAC.

int n,a,s,g;
vector<vector<pair<int,string> > > e;
string dp[40][500];

struct Node{
	string str; int cur;
	Node(int a,string b):cur(a),str(b){}
	Node(){}
	bool operator<(const Node &r)const{
		return str>r.str;
	}
};

int main(){
	while(cin>>n>>a>>s>>g,n)
	{
		e.clear(); e.resize(n);
		rep(i,a)
		{
			string str;
			int x,y; cin>>x>>y>>str;
			e[x].push_back(mp(y,str));
		}
		
		rep(i,n)rep(j,500)dp[i][j]="";
		priority_queue<Node> Q; Q.push(Node(s,""));
		while(!Q.empty())
		{
			int cur=Q.top().cur; string cstr=Q.top().str; Q.pop();
			if(cstr.size()>=500)continue;
			if(cur==g)
			{
				if(cstr.size()>=400)goto FAIL;
				cout<<cstr<<endl; goto END;
			}
			
			fr(i,e[cur])
			{
				int nxt=i->first; string nstr=cstr+i->second;
				if(nstr.size()>=500)continue;
				if(dp[nxt][nstr.size()]!=""&&dp[nxt][nstr.size()]<=nstr)continue;
				dp[nxt][nstr.size()]=nstr; Q.push(Node(nxt,nstr));
			}
		}
		FAIL:cout<<"NO"<<endl; END:;
	}
	return 0;
}