QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54981#4235. TransparencyKING_UT#AC ✓20ms4724kbC++202.9kb2022-10-11 19:59:092022-10-11 19:59:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-11 19:59:10]
  • 评测
  • 测评结果:AC
  • 用时:20ms
  • 内存:4724kb
  • [2022-10-11 19:59:09]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define repn(i,b) rng(i,1,b+1)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define a first
#define b second
#define eb emplace_back
template<class t>using vc=vector<t>;
template<class t, class u>bool chmin(t &a, u b){
	if(a > b){ a = b; return true;}
	else return false;
}
const int inf = 100000000;
int n, p, m;
vc<int>A;
bool in[55];
vc<pair<int,char>>edge[55];
int dd[55][55];
#define mp make_pair
using P=pair<int,int>;
using Q=pair<int,pair<int,P>>;

int dist[55][55][27];
void slv(){
	cin>>n>>p>>m;
	rep(i,p){
		int v;cin>>v;
		A.pb(v);
		edge[v].eb(n+1, 'a');
	}
	in[n+1] = 1;
	rep(a,55)rep(b,55)if(a!=b)dd[a][b]=inf;
	rep(i,m){
		int u,v;string s;
		cin>>u>>s>>v;
		edge[u].eb(v, s[0]);
		chmin(dd[u][v],1);
	}
	repn(k,n)repn(i,n)repn(j,n)chmin(dd[i][j],dd[i][k]+dd[k][j]);
	auto iscap=[](char c){
		return 'A'<=c and c<='Z';
	};
	rep(a,55)rep(c,55)rep(d,27)dist[a][c][d]=inf;
	priority_queue<Q,vc<Q>,greater<Q>>que;
	
	repn(i,n){
		if(edge[i].size() < 2) continue;
		rep(j, edge[i].size()){
			rep(k, edge[i].size()){
				if(j==k)continue;
				char c = edge[i][j].b;
				int to = edge[i][j].a;
				char c2 = edge[i][k].b;
				int to2 = edge[i][k].a;
				
				if(iscap(c) == iscap(c2)){
					if(iscap(c) and c != c2) continue;
					
					if(chmin(dist[to][to2][26],dd[1][i]*2+2)) que.push(mp(dist[to][to2][26], mp(to,mp(to2,26))));
				}
				else if(iscap(c)){
					if(chmin(dist[to][to2][c-'A'],dd[1][i]*2+2)) que.push(mp(dist[to][to2][c-'A'], mp(to,mp(to2,c-'A'))));
				}
			}
		}
	}
	while(!que.empty()){
		auto qq = que.top(); que.pop();
		int cs = qq.a;
		int u = qq.b.a;
		int v = qq.b.b.a;
		int t = qq.b.b.b;
		//cout<<u<<" "<<v<<" "<<t<<" "<<cs<<endl;
		if(dist[u][v][t] != cs) continue;
		for(auto to:edge[v]){
			int nxt = to.a;
			char c = to.b;
			if(!iscap(c)){
				if(dist[u][nxt][t] > cs+1){
					dist[u][nxt][t] = cs+1;
					que.emplace(cs+1, mp(u,mp(nxt, t)));
				}
			}
			else {
				int uu, vv, tt;
				if(t == 26) {
					uu = nxt, vv = u, tt = c-'A';
				}
				else if(t == c-'A') uu=u,vv=nxt,tt=26;
				else continue;
				
				if(dist[uu][vv][tt] > cs+1){
					dist[uu][vv][tt] = cs+1;
					que.emplace(cs+1, mp(uu, mp(vv,tt)));
				}
			}
		}
		if(t == 26){
			for(auto to:edge[u]){
				int nxt = to.a;
				char c = to.b;
				if(!iscap(c)){
					if(dist[nxt][v][t] > cs+1){
						dist[nxt][v][t] = cs+1;
						que.emplace(cs+1, mp(nxt,mp(v, t)));
					}
				}
				else {
					int uu, vv, tt;
					{
						uu = nxt,vv = v, tt = c-'A';
					}
					if(dist[uu][vv][tt] > cs+1){
						dist[uu][vv][tt] = cs+1;
						que.emplace(cs+1, mp(uu, mp(vv,tt)));
					}
				}
			}
		}
	}
	int ans=dist[n+1][n+1][26]-2;
	if(ans > inf/2) ans = -1;
	cout<<ans<<endl;	
}	
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	slv();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 4068kb

input:

4 1 8
3
1 F 1
1 A 2
2 b 1
2 F 3
2 d 3
3 B 3
3 y 4
4 d 1

output:

10

result:

ok single line: '10'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

4 1 8
3
1 F 1
1 A 2
2 b 1
2 F 3
2 d 3
3 B 3
3 y 4
4 d 4

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

5 2 5
1
5
1 i 2
2 c 3
3 p 4
4 c 1
1 I 5

output:

4

result:

ok single line: '4'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3896kb

input:

8 2 96
4
8
1 x 2
1 y 5
2 A 3
3 A 4
4 A 2
5 A 6
6 A 7
7 A 8
8 A 5
5 B 2
6 B 2
7 B 2
8 B 2
5 C 2
6 C 2
7 C 2
8 C 2
5 D 2
6 D 2
7 D 2
8 D 2
5 E 2
6 E 2
7 E 2
8 E 2
5 F 2
6 F 2
7 F 2
8 F 2
5 G 2
6 G 2
7 G 2
8 G 2
5 H 2
6 H 2
7 H 2
8 H 2
5 I 2
6 I 2
7 I 2
8 I 2
5 J 2
6 J 2
7 J 2
8 J 2
5 K 2
6 K 2
7 K 2
8...

output:

24

result:

ok single line: '24'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3884kb

input:

4 1 4
1
1 d 2
2 A 3
3 A 4
4 d 1

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3896kb

input:

7 1 8
1
1 d 2
2 A 3
3 A 4
4 d 1
1 A 5
5 d 6
6 d 7
7 A 1

output:

8

result:

ok single line: '8'

Test #7:

score: 0
Accepted
time: 2ms
memory: 4060kb

input:

1 1 1
1
1 a 1

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3948kb

input:

1 1 1
1
1 A 1

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3896kb

input:

2 1 2
2
1 a 2
1 b 2

output:

2

result:

ok single line: '2'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3972kb

input:

2 2 1
1
2
1 a 2

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3904kb

input:

4 2 3
3
4
1 A 2
2 a 3
2 b 4

output:

4

result:

ok single line: '4'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

50 1 149
50
1 A 2
2 B 3
3 C 4
4 D 5
5 E 6
6 F 7
7 G 8
8 H 9
9 I 10
10 J 11
11 K 12
12 L 13
13 M 14
14 N 15
15 O 16
16 P 17
17 Q 18
18 R 19
19 S 20
20 T 21
21 U 22
22 V 23
23 W 24
24 X 25
25 Y 26
26 Z 27
27 A 28
28 B 29
29 C 30
30 D 31
31 E 32
32 F 33
33 G 34
34 H 35
35 I 36
36 J 37
37 K 38
38 L 39
3...

output:

288

result:

ok single line: '288'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3916kb

input:

50 1 500
50
1 A 2
1 Z 2
1 Y 2
1 X 2
1 W 2
1 V 2
1 U 2
1 T 2
1 S 2
1 R 2
2 B 3
2 A 3
2 Z 3
2 Y 3
2 X 3
2 W 3
2 V 3
2 U 3
2 T 3
2 S 3
3 C 4
3 B 4
3 A 4
3 Z 4
3 Y 4
3 X 4
3 W 4
3 V 4
3 U 4
3 T 4
4 D 5
4 C 5
4 B 5
4 A 5
4 Z 5
4 Y 5
4 X 5
4 W 5
4 V 5
4 U 5
5 E 6
5 D 6
5 C 6
5 B 6
5 A 6
5 Z 6
5 Y 6
5 X 6
...

output:

533

result:

ok single line: '533'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3976kb

input:

50 1 500
50
1 A 2
1 Z 2
1 Y 2
1 X 2
1 W 2
1 V 2
1 U 2
1 T 2
1 S 2
1 R 2
2 B 3
2 A 3
2 Z 3
2 Y 3
2 X 3
2 W 3
2 V 3
2 U 3
2 T 3
2 S 3
3 C 4
3 B 4
3 A 4
3 Z 4
3 Y 4
3 X 4
3 W 4
3 V 4
3 U 4
3 T 4
4 D 5
4 C 5
4 B 5
4 A 5
4 Z 5
4 Y 5
4 X 5
4 W 5
4 V 5
4 U 5
5 E 6
5 D 6
5 C 6
5 B 6
5 A 6
5 Z 6
5 Y 6
5 X 6
...

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0
Accepted
time: 0ms
memory: 4056kb

input:

50 2 67
2
26
1 x 3
1 w 27
2 Z 3
3 Z 4
4 Z 5
5 Z 6
6 Z 7
7 Z 8
8 Z 9
9 Z 10
10 Z 11
11 Z 12
12 Z 13
13 Z 14
14 Z 15
15 Z 16
16 Z 17
17 Z 18
18 Z 19
19 Z 20
20 Z 21
21 Z 22
22 Z 23
23 Z 24
24 Z 25
25 Z 2
26 Z 27
27 Z 28
28 Z 29
29 Z 30
30 Z 31
31 Z 32
32 Z 33
33 Z 34
34 Z 35
35 Z 36
36 Z 37
37 Z 38
38...

output:

1200

result:

ok single line: '1200'

Test #16:

score: 0
Accepted
time: 20ms
memory: 4724kb

input:

50 5 2600
12
10
36
19
9
1 A 6
1 B 12
1 C 2
1 D 35
1 E 12
1 F 50
1 G 46
1 H 13
1 I 30
1 J 24
1 K 39
1 L 21
1 M 23
1 N 46
1 O 41
1 P 5
1 Q 43
1 R 24
1 S 43
1 T 8
1 U 50
1 V 41
1 W 47
1 X 11
1 Y 4
1 Z 26
1 a 33
1 b 34
1 c 30
1 d 37
1 e 4
1 f 42
1 g 22
1 h 14
1 i 44
1 j 18
1 k 50
1 l 16
1 m 24
1 n 41
1 ...

output:

2

result:

ok single line: '2'

Test #17:

score: 0
Accepted
time: 2ms
memory: 4060kb

input:

50 20 2600
8
45
50
40
10
13
27
2
21
34
31
25
36
46
39
15
16
20
35
26
1 A 45
1 B 39
1 C 21
1 D 10
1 E 22
1 F 50
1 G 18
1 H 23
1 I 19
1 J 40
1 K 17
1 L 45
1 M 42
1 N 10
1 O 35
1 P 45
1 Q 7
1 R 6
1 S 19
1 T 40
1 U 21
1 V 39
1 W 17
1 X 30
1 Y 31
1 Z 26
1 a 18
1 b 49
1 c 18
1 d 18
1 e 29
1 f 18
1 g 49
1 ...

output:

-1

result:

ok single line: '-1'

Test #18:

score: 0
Accepted
time: 11ms
memory: 4236kb

input:

50 20 2600
8
45
50
40
10
13
27
2
21
34
31
25
36
46
39
15
16
20
35
26
1 A 45
1 B 39
1 C 21
1 D 10
1 E 22
1 F 50
1 G 18
1 H 23
1 I 19
1 J 40
1 K 17
1 L 45
1 M 42
1 N 10
1 O 35
1 P 45
1 Q 7
1 R 6
1 S 19
1 T 40
1 U 21
1 V 39
1 W 17
1 X 30
1 Y 31
1 Z 26
1 a 18
1 b 49
1 c 18
1 d 38
1 e 29
1 f 18
1 g 49
1 ...

output:

5

result:

ok single line: '5'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3900kb

input:

9 2 15
6
3
1 A 2
1 f 3
2 c 4
2 H 6
2 b 5
3 G 1
4 H 4
4 e 7
4 D 1
5 d 8
5 L 3
7 F 9
8 F 9
9 H 6
9 p 1

output:

10

result:

ok single line: '10'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3840kb

input:

7 3 62
5
6
7
1 A 2
2 a 5
2 b 3
2 c 4
3 a 4
3 b 4
3 c 4
3 d 4
3 e 4
3 f 4
3 g 4
3 h 4
3 i 4
3 j 4
3 k 4
3 l 4
3 m 4
3 n 4
3 o 4
3 p 4
3 q 4
3 r 4
3 s 4
3 t 4
3 u 4
3 v 4
3 w 4
3 x 4
3 y 4
3 z 4
4 a 3
4 b 3
4 c 3
4 d 3
4 e 3
4 f 3
4 g 3
4 h 3
4 i 3
4 j 3
4 k 3
4 l 3
4 m 3
4 n 3
4 o 3
4 p 3
4 q 3
4 r 3...

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

9 2 15
6
3
1 A 2
1 f 3
2 c 4
2 H 6
2 b 5
3 G 1
4 H 4
4 e 7
4 D 1
5 d 8
5 L 3
7 r 9
8 t 9
9 H 6
9 p 1

output:

7

result:

ok single line: '7'

Test #22:

score: 0
Accepted
time: 1ms
memory: 3980kb

input:

24 4 30
2
3
15
23
1 B 2
2 C 3
3 D 2
3 f 4
3 A 17
4 A 5
5 g 6
5 R 2
6 Z 7
6 N 5
7 b 8
8 g 9
9 r 10
10 h 11
10 S 10
11 T 12
12 r 13
13 K 14
14 m 15
15 L 16
16 G 1
17 x 18
18 f 19
19 Z 20
20 V 2
20 T 21
21 K 22
22 m 23
23 F 24
24 C 1

output:

23

result:

ok single line: '23'

Test #23:

score: 0
Accepted
time: 0ms
memory: 4064kb

input:

7 2 6
4
7
1 f 2
2 A 3
3 b 4
1 g 5
5 A 6
6 c 7

output:

6

result:

ok single line: '6'

Test #24:

score: 0
Accepted
time: 2ms
memory: 4016kb

input:

26 4 32
2
3
15
25
1 B 2
2 C 3
3 D 2
3 f 4
3 A 17
4 A 5
5 g 6
5 R 2
6 Z 7
6 N 5
7 b 8
8 g 9
9 r 10
10 h 11
10 S 10
11 T 12
12 r 13
13 K 14
14 m 15
15 L 16
16 G 1
17 x 18
18 f 19
19 Z 20
20 V 2
20 T 21
21 K 22
22 m 23
23 i 24
24 k 25
25 F 26
26 C 1

output:

25

result:

ok single line: '25'

Test #25:

score: 0
Accepted
time: 2ms
memory: 3952kb

input:

4 1 4
4
1 m 2
2 X 3
3 a 4
3 b 4

output:

6

result:

ok single line: '6'

Test #26:

score: 0
Accepted
time: 15ms
memory: 4628kb

input:

50 1 2600
1
1 A 35
1 B 18
1 C 24
1 D 43
1 E 9
1 F 50
1 G 5
1 H 9
1 I 6
1 J 6
1 K 26
1 L 37
1 M 48
1 N 29
1 O 18
1 P 21
1 Q 50
1 R 33
1 S 47
1 T 27
1 U 31
1 V 39
1 W 27
1 X 24
1 Y 44
1 Z 33
1 a 16
1 b 7
1 c 38
1 d 7
1 e 49
1 f 12
1 g 47
1 h 20
1 i 5
1 j 42
1 k 29
1 l 14
1 m 32
1 n 28
1 o 28
1 p 30
1 ...

output:

-1

result:

ok single line: '-1'