The Most Powerful Spell
問題概要
n個の頂点とm個の辺からなるグラフを考える.
各辺にはラベルとして1文字から6文字までの文字列がある.
始点から終点までのパスのラベルを順に繋げたものを呪文という.
辞書順最小の呪文を求めよ.
ただし終点に到達不可能である場合や任意の呪文に対してそれより小さい呪文が存在する場合は”NO”と出力せよ.
解法
とりあえずループする場合は置いておく.
普通の最短路みたいに始点から順にDPしたら以下の図のような例で死ぬ.
これを解消するために各頂点に対して長さごとの最小の文字列を持つのが考えられそう.
しかしよく考えるとある頂点vから終点までの最小の呪文が決まってればどの辺から頂点vに来ればいいのかわかるので辺を逆向きにして終点からDPしてやれば良い.
dp[i] := 頂点iから終点までで追加される呪文の接尾辞の最小
呪文が無限に小さくなるループがある場合について考える.
ループがないなら呪文を作るパス上の頂点数は高々n.
各辺は最大6文字のラベルをもつので6n文字以上にはなりえない.
とりあえずBellman-Fordで7n回ぐらい回して上限を超えるようならNOとすればよい.
コード
(1169.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
using namespace std;
int n, m, s, g;
vector<pair<int,string>> G[64];
string dp[64];
string solve()
{
int lim = 6*n;
for (int lp = 0; lp < 7*n; lp++) {
bool updated = 0;
for (int i = 0; i < n; i++) {
if(i != g and dp[i] == "") continue;
for(auto &e: G[i]) {
if((e.first != g and dp[e.first] == "") or
dp[e.first] > e.second+dp[i]) {
dp[e.first] = e.second+dp[i];
updated = 1;
}
}
}
if(!updated) break;
if((int)dp[s].size() > lim) return "NO";
}
if(dp[s].size()) return dp[s];
return "NO";
}
bool input()
{
for (int i = 0; i < 64; i++) G[i].clear(), dp[i].clear();
cin >> n >> m >> s >> g;
for (int i = 0; i < m; i++) {
int u, v; string s;
cin >> u >> v >> s;
G[v].push_back(make_pair(u,s));
}
return n or m or s or g;
}
int main()
{
while(input()) cout << solve() << endl;
return 0;
}
|