QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #724341 | #5598. Profitable Trip | andahe | AC ✓ | 3711ms | 3764kb | C++20 | 1.0kb | 2024-11-08 12:12:41 | 2024-11-08 12:12:41 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define LL __int128_t
#define PB push_back
#define MK make_pair
#define Pair pair<int, int>
#define fi first
#define se second
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i <= _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i >= _##i; --i)
#define debug(x) cout<< "\033 -> "<<#x<<": "<<x<<endl
using namespace std;
const int N(2005);
#define X first
#define val second
vector<Pair> e[N];
int dis[N], die[N];
int main()
{
//freopen("1.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, w;
cin >> n >> m >> w;
FOR(i, 1, m)
{
int x, y, t; cin >> x >> y >> t;
e[x].PB(MK(y, t));
}
for(int i = 1; i <= n+1; ++i) dis[i] = -20000000;
dis[1] = 0;
int ans = dis[n+1];
for(int i = 1; i <= 1000000; ++i)
FOR(j, 1, n) if(dis[j] != dis[n+1])
{
for(auto to : e[j])
{
if(dis[to.X] < dis[j] + to.val)
dis[to.X] = min(dis[j] + to.val, w);
}
}
cout<<dis[n];
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 5ms
memory: 3708kb
input:
2 1 10 1 2 0
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 9ms
memory: 3652kb
input:
4 4 9 1 2 5 1 3 -2 2 4 1 3 4 10
output:
8
result:
ok single line: '8'
Test #3:
score: 0
Accepted
time: 8ms
memory: 3532kb
input:
4 4 7 1 2 5 1 3 -2 2 4 1 3 4 10
output:
7
result:
ok single line: '7'
Test #4:
score: 0
Accepted
time: 6ms
memory: 3588kb
input:
3 3 5 1 3 -10 3 2 2 2 3 -1
output:
4
result:
ok single line: '4'
Test #5:
score: 0
Accepted
time: 4ms
memory: 3672kb
input:
2 1 10 1 2 1
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 4ms
memory: 3584kb
input:
2 1 10 1 2 -1
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 4ms
memory: 3528kb
input:
2 2 10 1 2 1 2 1 -1
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 5ms
memory: 3716kb
input:
2 2 10 1 2 -1 2 1 2
output:
9
result:
ok single line: '9'
Test #9:
score: 0
Accepted
time: 4ms
memory: 3592kb
input:
2 2 10 1 2 2 2 1 -1
output:
10
result:
ok single line: '10'
Test #10:
score: 0
Accepted
time: 5ms
memory: 3652kb
input:
3 2 10 1 2 3 2 3 3
output:
6
result:
ok single line: '6'
Test #11:
score: 0
Accepted
time: 9ms
memory: 3576kb
input:
5 5 100 1 2 100 2 3 100 3 4 100 4 5 100 5 1 100
output:
100
result:
ok single line: '100'
Test #12:
score: 0
Accepted
time: 9ms
memory: 3588kb
input:
5 5 100 1 2 -100 2 3 -100 3 4 -100 4 5 -100 5 1 -100
output:
-400
result:
ok single line: '-400'
Test #13:
score: 0
Accepted
time: 2898ms
memory: 3684kb
input:
2000 2000 100 1748 1749 0 1361 1362 0 1671 1672 0 865 866 0 1288 1289 0 381 382 0 400 401 0 114 115 0 305 306 0 155 156 0 1026 1027 0 581 582 0 920 921 0 216 217 0 1274 1275 0 1449 1450 0 881 882 0 1006 1007 0 899 900 0 661 662 0 1564 1565 0 148 149 0 1140 1141 0 1824 1825 0 1109 1110 0 443 444 0 60...
output:
50
result:
ok single line: '50'
Test #14:
score: 0
Accepted
time: 2922ms
memory: 3744kb
input:
2000 2000 100 347 348 -100 476 477 -100 1004 1005 -100 1111 1112 -100 910 911 -100 1324 1325 -100 1845 1846 -100 1863 1864 -100 810 811 -100 1333 1334 -100 1386 1387 -100 33 34 -100 837 838 -100 1357 1358 -100 176 177 -100 1358 1359 -100 338 339 -100 1653 1654 -100 726 727 -100 1271 1272 -100 223 22...
output:
99
result:
ok single line: '99'
Test #15:
score: 0
Accepted
time: 2991ms
memory: 3764kb
input:
2000 2000 100 1926 1927 0 446 447 -100 296 297 -100 761 762 -100 1880 1881 0 1568 1569 0 223 224 -100 1334 1335 0 1492 1493 0 1411 1412 0 1237 1238 0 759 760 -100 260 261 -100 495 496 -100 1663 1664 0 1111 1112 0 127 128 -100 1606 1607 0 1466 1467 0 1745 1746 0 1549 1550 0 115 116 -100 76 77 -100 14...
output:
100
result:
ok single line: '100'
Test #16:
score: 0
Accepted
time: 2918ms
memory: 3760kb
input:
2000 2000 100 837 838 -31 1659 1660 -36 1274 1275 -4 302 303 22 1194 1195 71 1195 1196 -28 963 964 -14 402 403 5 153 154 12 1772 1773 58 1203 1204 -33 1881 1882 59 1860 1861 -33 1815 1816 -45 1102 1103 -30 1589 1590 20 50 51 91 1291 1292 44 136 137 -78 106 107 -54 88 89 -29 419 420 29 1710 1711 -74 ...
output:
50
result:
ok single line: '50'
Test #17:
score: 0
Accepted
time: 2553ms
memory: 3728kb
input:
2000 2000 100 1278 1191 -87 615 1430 -18 95 852 23 600 42 72 92 144 89 1420 1981 -29 530 1268 50 544 265 -63 934 373 27 1737 40 -45 114 767 0 1306 1530 40 312 429 -57 1108 1184 98 1414 1314 60 75 1629 5 1 484 37 1264 268 78 916 985 -20 1282 48 -25 1378 585 41 1452 1177 -19 357 431 -28 198 1567 5 152...
output:
100
result:
ok single line: '100'
Test #18:
score: 0
Accepted
time: 2333ms
memory: 3724kb
input:
2000 2000 100 1062 136 -98 443 874 -43 1363 724 39 1442 1118 -6 1123 660 40 1922 230 56 603 19 1 526 847 -89 1128 1983 -35 1372 1088 85 658 260 20 31 1678 100 1988 1889 31 562 152 45 45 199 53 1399 436 72 1342 1223 94 1257 856 -86 680 1407 4 241 1849 -59 854 1631 70 721 227 64 1797 250 4 1899 374 2 ...
output:
100
result:
ok single line: '100'
Test #19:
score: 0
Accepted
time: 3407ms
memory: 3720kb
input:
2000 2000 100 586 575 81 1216 49 77 986 1005 15 924 312 -58 1368 470 99 1647 1715 -61 781 754 -16 1623 1208 -72 693 60 -100 808 1505 6 758 1145 -20 479 755 38 1952 482 -37 914 486 -13 321 1708 83 1459 813 42 1483 1281 56 1510 1977 -67 690 1400 -12 1723 967 -89 1080 180 32 222 97 47 48 707 98 355 971...
output:
100
result:
ok single line: '100'
Test #20:
score: 0
Accepted
time: 3012ms
memory: 3744kb
input:
2000 2000 100 1639 1518 10 969 1146 70 816 1358 -66 1955 1066 32 1208 425 52 606 214 -51 127 177 -88 949 1164 -86 1225 1601 39 332 1817 -54 613 608 -92 1112 1582 -26 925 1028 -44 1640 1180 -37 362 1149 -48 1944 290 6 1067 1663 21 1280 1850 -19 742 1949 -19 1197 667 -46 1269 931 57 1497 41 17 352 319...
output:
100
result:
ok single line: '100'
Test #21:
score: 0
Accepted
time: 3711ms
memory: 3684kb
input:
2000 2000 100 1352 267 42 1580 22 9 50 1233 19 1249 1848 -44 1989 299 24 1951 1029 -99 1001 918 94 1079 1819 -81 317 323 95 159 277 33 1072 1880 -71 417 1892 -60 1982 1536 -76 1448 1650 79 396 1001 -63 745 1488 -90 292 121 45 1846 1529 -46 354 1146 80 1233 656 -20 1540 1701 -10 505 733 39 808 1689 7...
output:
-61
result:
ok single line: '-61'