QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#470367#5579. Bog of Eternal StenchZhouShangAC ✓448ms5772kbC++201.2kb2024-07-10 12:14:192024-07-10 12:14:20

Judging History

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

  • [2024-07-10 12:14:20]
  • 评测
  • 测评结果:AC
  • 用时:448ms
  • 内存:5772kb
  • [2024-07-10 12:14:19]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template<class A, class B> void cmx(A &x, B y) { x = max<A>(x, y);}
template<class A, class B> void cmn(A &x, B y) { x = min<A>(x, y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
int n,m,w[1<<20][5],d[1<<20],I=1e18;
int C(int k){
	for(int i=1;i<n;i++)
		d[i]=-1;
	d[n]=k;
	for(int j=1;j<=n;j++)
		for(int i=1;i<=m;i++){
			int x=w[i][0],y=w[i][1],z=w[i][2];
			if(d[x]==-1)
				continue;
			if(d[x]+z>=0)
				d[y]=max(d[y],d[x]+z);
		}
	for(int i=1;i<=m;i++){
		int x=w[i][0],y=w[i][1],z=w[i][2];
		if(d[x]==-1)
			continue;
		if(d[y]<d[x]+z)
			d[y]=I;
	}
	for(int j=1;j<=n;j++)
		for(int i=1;i<=m;i++){
			int x=w[i][0],y=w[i][1],z=w[i][2];
			if(d[x]==I)
				d[y]=I;
		}
	return d[1]!=-1;
}
signed main() {
	cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>w[i][1]>>w[i][0]>>w[i][2],w[i][2]=-w[i][2];
	int l=0,r=I,d;
	while(l<r)
		d=(l+r)/2,C(d)?r=d:l=d+1;
	cout<<l<<'\n';
}

详细

Test #1:

score: 100
Accepted
time: 382ms
memory: 5692kb

input:

1999 1999
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
10 11 1000000000
11 12 1000000000
12 13 1000000000
13 14 1000000000
14 15 1000000000
15 16 1000000000
16 17 1000000000
17 18 1000000000
18 19 1000000000
1...

output:

3

result:

ok single line: '3'

Test #2:

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

input:

4 4
1 2 5
1 3 -2
2 4 1
3 4 10

output:

6

result:

ok single line: '6'

Test #3:

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

input:

5 5
1 2 1000
2 3 -3
3 4 1
4 2 0
2 5 2

output:

3

result:

ok single line: '3'

Test #4:

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

input:

3 3
1 3 -10
3 2 2
2 3 -1

output:

0

result:

ok single line: '0'

Test #5:

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

input:

2 1
1 2 0

output:

0

result:

ok single line: '0'

Test #6:

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

input:

6 6
1 2 1000000000
2 6 -1
3 2 0
4 3 -1
3 5 -1
5 4 -1

output:

999999999

result:

ok single line: '999999999'

Test #7:

score: 0
Accepted
time: 12ms
memory: 5628kb

input:

46 1981
29 18 40
29 4 44
17 44 65
42 10 99
26 5 95
12 31 -3
18 4 100
27 34 69
5 35 22
29 9 -5
29 27 16
25 19 4
10 12 75
39 23 83
41 21 51
46 45 35
34 10 4
29 8 30
16 30 82
18 19 62
37 38 8
37 18 9
11 27 68
40 31 71
28 44 90
6 19 70
14 26 64
40 17 87
24 5 91
33 35 -1
10 2 23
22 35 17
14 18 31
45 28 7...

output:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 13ms
memory: 5612kb

input:

46 1981
29 18 47
29 4 71
17 44 26
42 10 50
26 5 13
12 31 41
18 4 57
27 34 83
5 35 76
29 9 0
29 27 21
25 19 2
10 12 99
39 23 47
41 21 91
46 45 67
34 10 75
29 8 86
16 30 58
18 19 4
37 38 70
37 18 -3
11 27 -2
40 31 84
28 44 88
6 19 84
14 26 12
40 17 52
24 5 95
33 35 63
10 2 60
22 35 67
14 18 17
45 28 1...

output:

7

result:

ok single line: '7'

Test #9:

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

input:

46 1981
29 18 10
29 4 47
17 44 43
42 10 6
26 5 27
12 31 13
18 4 25
27 34 14
5 35 72
29 9 55
29 27 87
25 19 72
10 12 21
39 23 8
41 21 20
46 45 40
34 10 63
29 8 64
16 30 72
18 19 63
37 38 35
37 18 1
11 27 95
40 31 47
28 44 41
6 19 12
14 26 11
40 17 21
24 5 60
33 35 91
10 2 13
22 35 34
14 18 14
45 28 6...

output:

1000000001

result:

ok single line: '1000000001'

Test #10:

score: 0
Accepted
time: 423ms
memory: 5612kb

input:

2000 1999
1205 1206 1000000000
1191 1192 1000000000
702 703 1000000000
1769 1770 1000000000
1060 1061 1000000000
469 470 1000000000
707 708 1000000000
1132 1133 1000000000
165 166 1000000000
1196 1197 1000000000
1214 1215 1000000000
1030 1031 1000000000
362 363 1000000000
1650 1651 1000000000
1736 1...

output:

1999000000000

result:

ok single line: '1999000000000'

Test #11:

score: 0
Accepted
time: 429ms
memory: 5772kb

input:

2000 1999
1205 1206 -1000000000
1191 1192 -1000000000
702 703 -1000000000
1769 1770 -1000000000
1060 1061 -1000000000
469 470 -1000000000
707 708 -1000000000
1132 1133 -1000000000
165 166 -1000000000
1196 1197 -1000000000
1214 1215 -1000000000
1030 1031 -1000000000
362 363 -1000000000
1650 1651 -100...

output:

0

result:

ok single line: '0'

Test #12:

score: 0
Accepted
time: 212ms
memory: 5700kb

input:

1002 2000
604 605 87
1 596 1000000000
353 352 -33
886 887 11
531 1002 63
236 237 2
1 354 1000000000
567 1002 51
84 85 75
599 1002 6
609 608 -90
517 516 -6
183 182 -101
827 826 -5
869 1002 34
991 1002 29
710 711 97
1 598 1000000000
323 1002 29
362 363 95
789 1002 25
780 781 74
212 213 86
853 852 -93
...

output:

6

result:

ok single line: '6'

Test #13:

score: 0
Accepted
time: 448ms
memory: 5688kb

input:

1894 1978
1154 1155 32
1142 1143 10
673 674 96
1694 1695 69
1015 1016 86
450 451 15
678 679 14
1085 1086 8
160 161 50
1145 1894 90
1163 1164 86
987 988 73
349 350 32
1581 1582 20
1663 1664 63
760 761 80
1358 1359 51
1 1102 1000000000
617 1894 11
692 693 33
1509 1510 98
1492 1493 59
404 405 26
1629 1...

output:

1978

result:

ok single line: '1978'

Test #14:

score: 0
Accepted
time: 259ms
memory: 5616kb

input:

1334 1999
805 804 -101
795 796 1000000000
469 470 1000000000
1181 1180 -8
708 709 30
314 315 52
473 472 -49
756 757 30
111 112 1000000000
799 798 -99
811 810 -39
688 689 16
243 242 -65
1101 1102 1000000000
1159 1158 -63
1321 1322 1000000000
946 947 85
798 799 98
431 430 -21
482 483 78
1052 1053 37
1...

output:

1000000010

result:

ok single line: '1000000010'

Test #15:

score: 0
Accepted
time: 400ms
memory: 5672kb

input:

1938 1981
1180 1181 47
1166 1167 73
688 689 44
1731 1732 61
1038 1039 34
460 461 40
693 694 20
1108 1109 12
163 164 94
1171 1172 21
1189 1146 -2133
1009 1010 84
355 356 21
1615 1616 48
1699 1700 43
1937 1938 1000000000
1387 1388 48
1170 1171 76
631 632 40
706 707 77
1542 1543 38
1524 1525 51
413 414...

output:

1000002229

result:

ok single line: '1000002229'

Test #16:

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

input:

3 3
1 3 1000
3 2 -100
2 3 99

output:

99

result:

ok single line: '99'