QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #876958 | #2501. Olympic Bus | Wansur# | 5 | 209ms | 8164kb | C++26 | 1.9kb | 2025-01-31 15:56:54 | 2025-01-31 15:56:56 |
Judging History
answer
#include <bits/stdc++.h>
#define ent '\n'
#define int long long
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 12;
const int inf = (int)1e12 + (int)1e8;
int cost[202][202];
int u[maxn], v[maxn], w[maxn], c[maxn];
int d1[maxn], dn[maxn];
bool used[maxn];
int n, m, k;
void work(int ver, int d[]) {
for(int i = 1; i <= n; i++) {
d[i] = inf;
used[i] = false;
}
d[ver] = 0;
for(int t = 0; t < n; t++) {
int v = 0;
for(int i = 1; i <= n; i++) {
if((!v || d[i] < d[v]) && !used[i]) {
v = i;
}
}
if(!v || d[v] == inf) break;
used[v] = true;
for(int i = 1; i <= n; i++) {
if(cost[v][i] < inf) {
d[i] = min(d[i], d[v] + cost[v][i]);
}
}
}
}
void solve() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> u[i] >> v[i] >> w[i] >> c[i];
}
int ans = inf;
for(int pos = 0; pos <= m; pos++) {
swap(u[pos], v[pos]);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cost[i][j] = inf;
}
cost[i][i] = 0;
}
for(int i = 1; i <= m; i++) {
cost[u[i]][v[i]] = min(cost[u[i]][v[i]], w[i]);
}
work(1, d1);
work(n, dn);
if(d1[n] < inf && dn[1] < inf) {
ans = min(ans, d1[n] + dn[1] + c[pos]);
}
swap(u[pos], v[pos]);
}
if(ans >= inf) ans = -1;
cout << ans << ent;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 164ms
memory: 8032kb
input:
200 1000 122 152 0 182437847 22 126 0 800796216 142 158 0 932784437 27 61 0 220600502 2 106 0 369508879 150 200 0 576962057 99 9 0 588062163 101 72 0 148003923 9 182 0 732139947 84 88 0 720592694 198 161 0 151363245 89 187 0 214138025 160 150 0 82621350 63 170 0 665493133 135 144 0 571301198 118 29 ...
output:
0
result:
ok single line: '0'
Test #2:
score: 5
Accepted
time: 3ms
memory: 5992kb
input:
200 250 87 77 0 413690178 44 146 0 580238372 96 86 0 471635629 76 37 0 460314897 36 26 0 797795878 186 196 0 340458462 137 148 0 8238512 63 102 0 83585569 128 92 0 355539314 111 136 0 941271932 120 25 0 670904911 68 143 0 789757256 50 24 0 57273302 166 33 0 961114401 151 122 0 88660198 162 71 0 2027...
output:
-1
result:
ok single line: '-1'
Test #3:
score: 5
Accepted
time: 207ms
memory: 5992kb
input:
200 1000 32 195 208991 761039285 174 149 435536 435440777 109 29 693056 976975992 47 44 590890 186457226 80 65 353546 61953096 163 79 124971 309842392 5 82 341956 789963665 124 175 650665 600626885 46 79 450500 56179506 78 99 803108 312872894 194 48 926872 609270327 47 31 865000 911848359 113 46 598...
output:
2437514
result:
ok single line: '2437514'
Test #4:
score: 5
Accepted
time: 203ms
memory: 8036kb
input:
200 1000 200 164 902271 53884170 200 56 160646 471284489 118 17 548821 676285924 75 86 463453 741371140 124 183 677876 745454313 78 118 829257 377444281 26 137 315614 193865748 191 39 355032 923063487 29 171 281727 396954281 147 105 785551 455760667 161 19 730891 528269519 144 49 352247 321053381 15...
output:
2797127
result:
ok single line: '2797127'
Test #5:
score: 5
Accepted
time: 4ms
memory: 7780kb
input:
32 1000 16 15 124290 308896 6 18 503091 464441 5 26 710425 73322 30 9 502128 77143 15 19 378107 360904 20 10 857413 475127 23 19 732182 158395 30 11 646521 847592 10 21 400052 514680 16 20 254701 362685 29 2 302402 652641 1 31 171216 961419 9 24 15977 616364 10 32 635354 712012 6 20 16048 515031 7 1...
output:
298489
result:
ok single line: '298489'
Test #6:
score: 5
Accepted
time: 3ms
memory: 8040kb
input:
200 250 196 111 774995 586221052 17 177 831588 26974950 164 84 714701 648810834 17 13 742157 618387545 85 147 888921 259372421 154 15 298654 78188800 173 169 110484 573489855 127 64 365056 388013540 82 151 610677 517180859 159 123 947809 628375445 39 107 479215 223508800 111 182 697301 882646990 197...
output:
-1
result:
ok single line: '-1'
Test #7:
score: 5
Accepted
time: 0ms
memory: 7728kb
input:
2 1 1 2 295445 873561966
output:
-1
result:
ok single line: '-1'
Test #8:
score: 5
Accepted
time: 0ms
memory: 7776kb
input:
2 1 2 1 237201 424844240
output:
-1
result:
ok single line: '-1'
Test #9:
score: 5
Accepted
time: 3ms
memory: 7780kb
input:
2 1000 1 2 402668 186853963 1 2 735949 714240522 1 2 890366 761125200 1 2 951814 194495679 1 2 99029 557310684 1 2 617215 419379276 1 2 549225 178839633 1 2 355323 573589917 1 2 937541 928362249 1 2 868758 781946304 1 2 767929 303821251 1 2 626242 479948170 1 2 813810 44652483 1 2 171218 226464554 1...
output:
716875
result:
ok single line: '716875'
Test #10:
score: 5
Accepted
time: 209ms
memory: 8036kb
input:
200 1000 178 18 403199 745306 138 157 793234 968778 50 142 870390 93621 109 67 999704 979412 116 22 9321 687633 1 63 899030 755605 121 60 745634 834563 80 66 360811 865058 88 193 822514 784092 172 92 670903 360385 152 32 902998 468642 170 106 4454 31995 179 127 691910 841564 42 16 377120 79150 40 30...
output:
2031511
result:
ok single line: '2031511'
Test #11:
score: 5
Accepted
time: 209ms
memory: 5992kb
input:
200 1000 102 34 9765 492340 40 51 974965 910912 150 79 622386 108020 5 24 923983 390013 124 147 685146 380706 196 166 486 13100 11 192 391732 303741 103 182 3396 952309 104 196 8579 92828 14 108 456347 495057 71 158 524650 639348 48 171 489031 870958 106 123 757519 469153 49 119 314 286212 38 119 63...
output:
1952385
result:
ok single line: '1952385'
Test #12:
score: 5
Accepted
time: 207ms
memory: 5996kb
input:
200 1000 147 58 8369 679288 127 43 561908 768977 190 37 225224 36886 72 61 976059 334027 134 107 495719 115758 175 198 8231 409372 77 37 873272 382176 150 200 6384 475014 16 92 209657 234021 87 42 628084 846766 84 64 980603 242788 60 53 997 3242 145 22 603669 412271 128 155 680529 398679 181 78 7791...
output:
2118142
result:
ok single line: '2118142'
Test #13:
score: 5
Accepted
time: 124ms
memory: 6000kb
input:
200 1000 11 130 791191 404176588 11 122 563555 56058088 30 152 148445 539862143 198 103 120872 72731844 104 84 249798 911595238 43 170 461746 606803643 131 166 766080 370530123 162 133 422234 55245031 49 17 482082 886905498 23 57 368967 740007727 82 16 852072 87081727 138 117 178612 293980051 197 60...
output:
10868146
result:
ok single line: '10868146'
Test #14:
score: 5
Accepted
time: 151ms
memory: 7908kb
input:
200 1000 33 168 764973 324367398 12 123 829830 598733437 131 111 376329 424202715 54 69 590082 795737748 126 142 966806 201764048 5 123 239136 712318652 151 128 288844 25751551 57 26 498394 373677403 131 2 857656 108946841 106 149 377721 830446828 58 188 330376 582002477 34 119 188444 757594629 175 ...
output:
-1
result:
ok single line: '-1'
Test #15:
score: 5
Accepted
time: 143ms
memory: 8160kb
input:
200 1000 160 124 613071 696182916 159 74 870937 706697190 44 186 440707 437083079 2 21 819503 733229200 138 175 692401 889850109 200 73 624745 475215360 187 71 294075 625347482 166 187 340630 873369287 58 98 558584 834147686 96 121 537329 89196024 7 78 943459 205771934 47 38 675193 450415293 155 173...
output:
150860521
result:
ok single line: '150860521'
Test #16:
score: 5
Accepted
time: 144ms
memory: 5992kb
input:
200 1000 139 85 612404 678107446 193 167 370424 299825457 133 80 337021 807058141 166 76 848124 361695195 91 56 488427 208862978 18 181 906083 917428464 197 58 724726 876386772 132 170 819233 420219361 144 34 261383 50158753 64 132 565045 986404728 63 143 622103 188681921 46 57 468678 33496975 12 63...
output:
69441539
result:
ok single line: '69441539'
Subtask #2:
score: 0
Time Limit Exceeded
Test #17:
score: 0
Time Limit Exceeded
input:
200 50000 92 72 987034 981351 92 72 987034 428035 95 16 263441 869630 95 16 263441 274419 18 67 742896 495941 18 67 742896 773584 89 7 456457 702434 89 7 456457 631522 52 193 188333 207969 52 193 188333 151198 32 144 801401 523873 32 144 801401 485433 114 30 945638 685397 114 30 945638 387101 177 94...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #31:
score: 21
Accepted
time: 159ms
memory: 8164kb
input:
200 1000 29 42 0 73206665 155 127 0 684640269 50 198 0 321195054 144 61 0 823740117 102 146 0 503128895 56 38 0 739648322 181 24 0 720383720 197 37 0 235418116 57 184 0 493283302 125 96 0 845930225 11 59 0 18751364 101 122 0 175819721 123 151 0 99670888 111 194 0 526645991 132 64 0 904239661 103 173...
output:
0
result:
ok single line: '0'
Test #32:
score: 21
Accepted
time: 11ms
memory: 5996kb
input:
200 250 72 162 0 953534115 152 94 0 541492633 58 118 0 389246378 118 137 0 266112508 21 100 0 546059320 26 28 0 396924657 155 69 0 955241958 123 102 0 483117471 160 39 0 787307136 31 80 0 230131728 33 69 0 459221426 149 126 0 356240138 128 99 0 991905541 7 57 0 28752914 149 6 0 761950451 23 150 0 66...
output:
-1
result:
ok single line: '-1'
Test #33:
score: 0
Time Limit Exceeded
input:
200 39000 5 128 0 263267641 153 85 0 899842112 187 180 0 595861423 104 180 0 342805606 46 128 0 402084500 149 35 0 569501214 103 161 0 260423816 141 134 0 45988579 46 84 0 733407435 102 72 0 411807981 16 93 0 653975947 136 122 0 802943341 194 12 0 486663003 15 39 0 756041482 114 102 0 81270200 29 17...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%