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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
| #include <bits/stdc++.h>
#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define debug(...) fprintf (stderr, __VA_ARGS__)
using std :: cin;
using std :: cout;
using std :: endl;
using std :: cerr;
using i64 = long long;
const int P = 1e9 + 7;
inline int mod(int x) { return x + (x >> 31 & P); }
inline void sub(int &x, int y) { x = mod(x - y); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline int add(int x, int y) { return mod(x + y - P); }
inline int dec(int x, int y) { return mod(x - y); }
inline int power(int x, int k) {
int res = 1; if (k < 0) k += P - 1;
while (k) { if (k & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; k >>= 1; }
return res;
}
const int N = 2e6 + 5;
int n, m, k;
int endpos[N];
std :: vector<std :: pair<int, char> > e[N], g[N];
int vis[N], bj[N];
void dfs1 (int x) {
if (vis[x]) return ;
vis[x] = 1;
for (auto [y, c] : g[x]) dfs1 (y);
}
std :: vector<char> stk;
int dep[N], flg = 0;
int nowend;
std :: string nowans;
int in[N];
void dfs2 (int x, int mxd, int mxp) {
if (flg) return ;
bj[x] = 1; in[x] = 1;
for (auto [y, c] : e[x]) {
if (flg) return ;
if (! bj[y]) dep[y] = dep[x] + 1,stk.push_back (c), dfs2 (y, vis[y] ? dep[y] : mxd, vis[y] ? y : mxp), stk.pop_back();
else {
if (dep[y] <= mxd && in[y]) {
flg = 1;
stk.push_back (c);
for (int i = dep[y]; i <= mxd - 1; i ++)
stk.push_back (stk[i]);
nowend = mxp;
for (int i = 0; i < stk.size(); i ++) nowans += stk[i];
return ;
}
}
}
in[x] = 0;
}
std :: vector<char> rec;
void dfs3 (int x) {
if (vis[x]) return ;
vis[x] = 1;
if (x == nowend) {
std :: reverse(rec.begin(), rec.end());
cout << nowans;
for (char ch : rec) cout << ch;
cout << endl;
exit (0);
}
for (auto [y, ch] : g[x]) rec.push_back (ch), dfs3 (y), rec.pop_back();
}
int main() {
std :: ios :: sync_with_stdio(false);
cin >> n >> m >> k;
lep (i, 1, k) {
int x;
cin >> x;
endpos[x] = 1;
}
lep (i, 1, m) {
int x, y; char c;
cin >> x >> y >> c;
e[x].push_back ( {y, c} );
g[y].push_back ( {x, c} );
}
lep (i, 1, n) if (endpos[i] && ! vis[i]) {
dfs1 (i);
}
dfs2 (1, vis[1] ? 0 : (int) - 1e9, vis[1] ? 1 : 0);
if (flg == 0) return cout << -1 << endl, 0;
memset (vis, 0, sizeof (vis));
lep (i, 1, n) if (endpos[i] && ! vis[i]) {
dfs3 (i);
}
assert (0);
return 0;
}
|
