ACM-ICPC 2010国内予選 E. 最強の呪文(その2)

ACM-ICPC

E. 最強の呪文

下に書いた話で、

  • 倍くらい調べればループを使って辞書順を小さくする文字列が見つかる
  • ゴール以外で6*(ノード数)くらいでループなしより辞書順で小さくなったら"NO"


とか言ってるので，倍くらい調べなくて良い事に気付きました。


"NO"になる判定法は、

  • 1〜6*(ノード数-1)文字以内で辞書順最小の呪文sを探しておく
  • ゴールに到達出来るノードで，sより辞書順で小さい呪文が作れたら"NO"
    • そこからゴールに到達すればsより小さい呪文ができる
    • その文字列はループを含むので，いくらでも辞書順を小さくできる


としておけば良いようです。

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef vector< vector< pair<int, string> > > Graph;

class Node{
public:
    int pos; string str;
    Node(int pos, string str) : pos(pos), str(str) {}
    bool operator < (const Node &nd) const { return str > nd.str; }
};

int main(){
    int n, a, s, g;
    bool con[40][40];
    bool visit[240][40];
    string str[240][40];
    while(cin >> n >> a >> s >> g, n){
        Graph graph(n);
        memset(con, false, sizeof(con));
        memset(visit, false, sizeof(visit));
        for(int i=0;i<a;i++){
            int x, y; string lab; cin >> x >> y >> lab;
            graph[x].push_back(make_pair(y,lab));
            con[x][y] = true;
        }
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(con[i][k]&&con[k][j]) con[i][j] = true;
        priority_queue<Node> qu; qu.push(Node(s, ""));
        while(!qu.empty()){
            Node nd = qu.top(); qu.pop();
            int pos = nd.pos, size = nd.str.size();
            if(visit[size][pos]) continue;
            visit[size][pos] = true;
            str[size][pos] = nd.str;
            for(int i=0;i<graph[pos].size();i++){
                int npos = graph[pos][i].first;
                if(size + graph[pos][i].second.size() >= 6*n) continue;
                string nstr = nd.str + graph[pos][i].second;
                if(!visit[nstr.size()][npos])
                    qu.push(Node(npos, nstr));
            }
        }
        string ans = "";
        for(int i=0;i<6*(n-1);i++){
            if(!visit[i][g]) continue;
            if(ans == ""||ans > str[i][g]) ans = str[i][g];
        }
        for(int i=0;i<n;i++){
            if(!con[i][g]) continue;
            for(int j=6*(n-1);j<6*n;j++)
                if(visit[j][i]&&str[j][i]<ans) ans = "";				
        }
        cout << (ans!="" ? ans : "NO") << endl;
    }
}