AOJ 1169 : The Most Powerful Spell

問題リンク：The Most Powerful Spell | Aizu Online Judge

問題概要：
辺に文字列をコストとしてもつ有向グラフが与えられる
スタートのノード番号とゴールのノード番号が与えられるので最小コストで到達した時のコスト（文字列）を出力せよ
最小コストが存在しない（無限に小さくなる or 到達しない）場合は"NO"と出力せよ
ここで、コストが小さいとは文字列が辞書順で小さいことをいう

解法：
ACM-ICPC 2010 Japan Domestic 問題E - cafelier@SRM - TopCoder部
を参考にしました

簡単に説明すると、
負の閉路を検出するためにベルマンフォード法を使いましたが、普通にスタートからゴールまで行くと負の閉路を検出できません（理由は上のサイトにあります）
なので全ての辺を逆向きにしてゴールからスタートへ行きました

なおかつ、負の閉路がスタートからゴールまでの経路と関係ない場所にあった場合にはそれを検出しないようにしました
if(行き先 == ゴール && ループ回数 >= ノードの数)return "found";

つまり、これから更新する場所がゴールで、ループの回数がノード数を越えているならばスタートからゴールまでの経路上に負の閉路が存在するということです

なお、負の閉路検出用のループはノード数回だけのループではいけません
（これまた理由は上のサイトにあります）

コード：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cassert>
#include<sstream>
#include<deque>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX 50
#define MAX2 404
#define inf (string(400,'Z'))
using namespace std;
struct P
{
  int from,to;
  string cost;
  P(int from=-1,int to=-1,string cost="$"):from(from),to(to),cost(cost){}
};
int V,E,s,g;
P es[MAX2];
string d[MAX];

bool check(string a,string b)//a < b?
{
  return a < b;
}

bool Bellman_Ford()
{
  rep(i,MAX)d[i]="$";
  rep(i,E)
    if(es[i].from == s && (d[es[i].to] == "$" || d[es[i].to] > es[i].cost))
      d[es[i].to] = es[i].cost;

  int loop = V*6;
  rep(xyz,loop)
    {
      rep(i,E)
	{
	  P p = es[i];

	  if(d[p.from] == "$")continue;
	  if(d[p.to] == "$")
	    {
	      d[p.to] = p.cost + d[p.from];
	      if(p.to == g && xyz >= V)return true;
	      continue;
	    }

	  if(d[p.to] != "$" && check(p.cost + d[p.from],d[p.to]))
	    {
	      d[p.to] = p.cost + d[p.from];

	      if(p.to == g && xyz >= V)return true;
	    }

	}
    }
  return false;
}

int main()
{
  //謎の挙動
  //cout << ("ace" < "abc") << endl;
  //cout << ("ace" < "abc") << " ; " << min("ace","abc") << endl;
  while(cin >> V >> E >> g >> s,V|E|s|g)
    {
      rep(i,E)
	cin >> es[i].to >> es[i].from >> es[i].cost;
      if(Bellman_Ford())
	{
	  cout << "NO" << endl;
	  continue;
	}
  
      if(d[g] == "$")cout << "NO" << endl;
      else          cout << d[g] << endl;
    }
  return 0;
}