QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #93773 | #6147. 赛车竞技 | Renshey | 100 ✓ | 321ms | 11160kb | C++23 | 1.7kb | 2023-04-02 10:37:57 | 2023-04-02 10:37:59 |
Judging History
answer
#include <bits/stdc++.h>
const long long inf = 1LL << 60;
int n, m, q;
long long a[82][82], E1[82][82][70], E2[82][82][70];
signed main()
{
scanf("%d%d%d", &n, &m, &q);
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
E1[u][v][0] = E2[u][v][0] = (u == v) ? 0 : inf;
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
E1[u][v][1] = inf;
for (int i = 1; i <= m; i++)
{
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
scanf("%lld", &a[u][v]);
for (int x = 1; x <= n; x++)
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
a[u][v] = std::min(a[u][v], a[u][x] + a[x][v]);
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
E1[u][v][1] = std::min(E1[u][v][1], a[u][v]);
}
for (int k = 2; k <= 64; k++)
{
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
E1[u][v][k] = E1[u][v][k - 1];
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
for (int x = 1; x <= n; x++)
E1[u][v][k] = std::min(E1[u][v][k], E1[u][x][k - 1] + E1[x][v][1]);
}
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
E2[u][v][1] = E1[u][v][64];
for (int k = 2; k <= 64; k++)
{
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
E2[u][v][k] = E2[u][v][k - 1];
for (int u = 1; u <= n; u++)
for (int v = 1; v <= n; v++)
for (int x = 1; x <= n; x++)
E2[u][v][k] = std::min(E2[u][v][k], E2[u][x][k - 1] + E2[x][v][1]);
}
for (int u, v, k; q--;)
{
scanf("%d%d%d", &u, &v, &k);
k++;
long long ans = inf;
for (int x = 1; x <= n; x++)
ans = std::min(ans, E1[u][x][k % 64] + E2[x][v][k / 64]);
printf("%lld\n", ans);
}
return 0;
}
詳細信息
Test #1:
score: 4
Accepted
time: 3ms
memory: 5716kb
input:
5 4 40 0 10075 20104 10059 20043 9943 0 9993 19840 9923 20127 10038 0 29843 19906 9977 20099 29960 0 29945 20089 9995 19896 29811 0 0 9925 19849 10026 20060 9965 0 10100 20056 9960 19941 10082 0 30033 19872 10045 20120 29867 0 30107 19967 10074 20092 29995 0 0 10002 20113 9900 19901 10074 0 9915 198...
output:
9915 9925 19896 9943 29832 10006 10006 9900 19840 19861 19859 19872 19848 9923 19840 29759 29763 29763 29759 9900 9925 9915 29759 9915 29761 9943 19896 19885 29764 19840 29759 19840 29759 19861 19896 19840 9900 29763 19861 9923
result:
ok 40 lines
Test #2:
score: 4
Accepted
time: 3ms
memory: 5788kb
input:
6 4 50 0 10021 19954 19932 29963 30199 10094 0 9945 10035 20145 19963 19960 10048 0 20039 10051 29888 20026 10005 20122 0 29796 10022 29951 20082 10027 30023 0 40142 30190 19868 30136 10062 40052 0 0 9997 19994 19830 30112 30219 9974 0 10023 10003 19982 20118 20061 10069 0 20054 9991 29851 20128 998...
output:
9977 9902 10014 29730 19898 9981 9921 19847 29759 9945 9977 10014 19829 19830 9971 29823 19876 9991 9901 29730 19849 29759 10014 39657 19889 9921 29819 9902 29759 9991 19898 9991 29851 29811 29926 29823 39657 19898 19898 19829 9991 39657 29730 19830 9931 19898 19898 29851 19876 19830
result:
ok 50 lines
Test #3:
score: 4
Accepted
time: 0ms
memory: 7844kb
input:
9 10 18 0 10037 9970 20038 20015 29975 40026 50131 39830 9943 0 20097 9984 30081 39775 49976 59783 49876 9925 20153 0 30178 10077 20164 30113 40232 30016 20038 10016 30159 0 40193 49765 59951 70100 60207 19856 29829 10087 40228 0 9963 20161 29903 19869 29800 40119 20082 49924 10048 0 10053 20034 100...
output:
29784 9903 29768 39681 29751 29776 29744 9906 19814 19814 9931 9906 29748 19840 29776 29766 19836 59523
result:
ok 18 lines
Test #4:
score: 4
Accepted
time: 3ms
memory: 5832kb
input:
10 9 15 0 10021 19887 30151 29854 29837 39737 40097 49811 49661 10043 0 9930 19862 20019 20039 29778 29918 39882 40189 19962 10090 0 10090 10054 9910 19959 19857 29783 30236 29985 19857 10050 0 19881 19861 29827 30034 40281 39961 30092 19857 10011 19987 0 20031 29870 29769 40124 39737 30229 19892 99...
output:
39674 39630 9986 19842 29758 29756 29749 49576 29745 39670 29727 29726 29761 29744 19818
result:
ok 15 lines
Test #5:
score: 4
Accepted
time: 4ms
memory: 5792kb
input:
10 10 20 0 9984 19904 10005 30081 19872 20090 40290 49682 29855 10030 0 9905 20134 19836 30185 29999 30205 40161 39808 19982 10074 0 29921 9996 40156 39787 19875 29809 50206 10051 20080 30200 0 40234 10053 9904 50074 60408 20169 29959 20062 9937 39990 0 49705 49960 10072 20032 60265 19831 29899 4026...
output:
39631 19822 39649 29744 19826 9925 29724 9905 39659 39666 19825 19815 39631 79305 9916 19819 19808 29717 19826 29723
result:
ok 20 lines
Test #6:
score: 4
Accepted
time: 13ms
memory: 8248kb
input:
20 12 50000 0 9957 9996 10052 20028 19982 19827 30052 30154 39706 49966 39787 50355 59970 50306 59768 70417 79642 79560 90474 10017 0 19964 19829 30001 30130 30094 39921 39853 50340 60413 50236 59746 69731 60383 69980 79501 89557 90164 100334 10052 20061 0 19946 9982 30211 30211 40221 40266 49638 59...
output:
29762 29760 19806 59532 49563 9904 109149 9900 59555 79435 79337 49686 89317 49588 19821 19831 19800 69420 19811 9910 49576 19833 69466 89303 69485 79362 39662 79337 39647 89418 39650 49608 19805 19829 119084 79362 69420 99265 39672 89303 69424 109143 89307 59610 19808 59587 19831 9905 9900 49598 99...
result:
ok 50000 lines
Test #7:
score: 4
Accepted
time: 25ms
memory: 7784kb
input:
5 4 100000 0 10060 19867 20076 30047 10079 0 9945 9909 20139 19847 10069 0 19964 30088 20101 10042 20115 0 10037 29974 20055 29976 10049 0 0 10062 20061 19991 30114 9996 0 9960 10043 20072 19940 10034 0 20098 29762 19947 9959 19964 0 9939 30182 19887 30102 10021 0 0 10031 19902 20015 29824 10013 0 1...
output:
19812 9959 19848 29777 19917 10021 29777 19887 9903 9973 29824 19867 19946 9973 9909 9903 9959 9959 9939 19847 9959 19917 9945 29847 10021 19946 19848 19887 29762 29751 9959 9909 19954 19840 19867 19926 19867 9973 19926 9959 29777 10017 9973 9909 29824 9939 19847 10021 9959 29824 9959 29762 10021 19...
result:
ok 100000 lines
Test #8:
score: 4
Accepted
time: 24ms
memory: 8168kb
input:
23 14 100000 0 9983 20158 30207 19992 29861 29772 39930 39914 49868 60042 69935 80509 90494 79556 89870 99916 109404 120633 129383 119775 130643 140306 10029 0 9936 19870 10092 19928 19869 30187 29937 40113 49669 60055 70280 79823 70395 79945 89699 99466 109581 119398 110071 119387 130211 19898 1003...
output:
109243 49582 9917 109125 89248 49572 19808 59519 39733 29751 39680 9904 69414 59470 89298 59489 9901 19807 79392 109213 29748 9913 79391 69435 89285 9913 119095 79437 69519 59533 89361 39671 79343 119156 59498 39665 39697 39735 59606 39653 139045 49589 29762 89305 109157 129068 29726 39686 99304 396...
result:
ok 100000 lines
Test #9:
score: 4
Accepted
time: 54ms
memory: 5944kb
input:
6 4 200000 0 9901 9939 9917 20065 19975 9929 0 19830 19875 9908 29911 9977 20003 0 20070 30077 10098 9975 19847 20071 0 29797 29848 19985 9909 30010 29791 0 40098 19877 30082 9916 30035 40210 0 0 9973 9932 9910 20134 20159 10080 0 20144 20107 9993 30232 10003 20127 0 20143 30004 9963 9929 19965 1986...
output:
39638 9909 29755 29729 9929 19861 9916 19869 29739 29755 19820 29729 9910 9910 9917 19830 19885 9929 9916 19861 29770 29786 29755 9917 19818 9910 19820 9903 9977 19830 29726 19878 9910 19878 9977 39678 29779 19809 39678 39692 9901 19878 19885 9903 19809 19826 9910 9916 39638 9917 19818 29786 29786 1...
result:
ok 200000 lines
Test #10:
score: 4
Accepted
time: 87ms
memory: 8104kb
input:
25 15 200000 0 9964 20057 10059 19969 29986 30042 30039 40290 49826 50277 60304 60059 60131 70234 80406 70032 79750 89580 90457 90529 99969 100112 109788 109685 10046 0 9922 20142 10004 19967 20037 20132 30025 39767 40180 49739 49937 50327 59827 70363 60091 69656 79957 79935 80040 89874 90389 99470 ...
output:
99274 79447 29743 49573 9909 79382 19843 59459 69501 29738 19831 59587 9915 59593 59511 19844 69402 29748 29780 39707 19801 39643 89390 99184 9909 29756 89301 29746 59531 49642 89335 99302 19821 9949 89295 49641 29757 59560 69424 79366 9906 109276 9906 79369 49622 9927 19830 29769 69468 99293 59590 ...
result:
ok 200000 lines
Test #11:
score: 4
Accepted
time: 94ms
memory: 10932kb
input:
75 75 60 0 10010 9973 9954 20094 19861 20068 30136 30049 30053 39844 39907 49956 50217 50074 59740 59961 69630 69763 70158 80481 80108 80041 90494 89822 99870 99831 109447 110061 119761 120255 129238 130581 140566 140250 149463 150719 159254 170387 169959 180777 190073 180810 190860 201060 210947 21...
output:
237650 138798 405999 19802 138635 59413 108937 287531 69329 79217 188290 89270 307455 69321 49514 29702 217838 39606 108935 39619 217847 188138 168746 29708 9901 49503 49508 59406 148528 49505 138625 19801 207943 19800 178232 59409 128732 207946 9901 227795 128726 267349 178240 198177 217836 99014 2...
result:
ok 60 lines
Test #12:
score: 4
Accepted
time: 114ms
memory: 10656kb
input:
75 80 80 0 10069 20011 10068 19935 30117 29787 40156 39850 40283 50354 50194 50050 59830 59686 69919 69744 69657 80209 80207 90120 90005 90178 100489 100306 109854 109572 119327 120287 120356 129256 129713 130363 139583 139606 149761 149740 160105 160043 170584 170344 179880 179451 190329 199753 209...
output:
89110 168580 128735 79204 39607 89274 287368 99015 69315 128714 118820 69303 99016 108916 138622 89110 69304 198558 217838 198028 79215 227739 39607 89107 59528 99132 128721 79204 69309 207978 89112 237830 207932 128991 108910 118812 39601 227743 138625 178232 79203 277247 168325 89110 148666 158431...
result:
ok 80 lines
Test #13:
score: 4
Accepted
time: 130ms
memory: 10940kb
input:
80 75 90 0 9941 19865 9981 20004 20142 19907 29881 29769 29909 40165 40022 50059 60347 60162 59595 70254 80278 80416 90488 99568 109711 120128 109678 120405 129280 140095 140217 139603 149633 149624 150425 159707 160482 169981 170816 169652 180327 189134 201009 209903 199075 209807 219919 210255 220...
output:
267532 59490 336971 178242 188142 158439 19802 178574 198323 307272 356486 247553 99022 19805 59514 19802 79234 277279 9905 29714 19805 227845 39607 178543 217850 49506 118818 128730 118825 307124 29703 178229 69314 89132 128743 99011 207940 247554 267366 138638 198209 89119 69312 128721 89109 69306...
result:
ok 90 lines
Test #14:
score: 4
Accepted
time: 118ms
memory: 11160kb
input:
80 80 100 0 9954 20085 10063 19872 19987 20163 29812 39991 30034 49923 49918 59909 59581 69550 80511 79867 80324 89599 99702 109714 109776 120411 130126 129317 130291 139324 149555 159532 159083 159406 169697 169339 180961 180396 189635 200026 211007 199610 210041 220576 209726 230753 220666 239046 ...
output:
79206 39603 49514 168320 39601 227753 118811 69323 178441 227723 168389 178252 336890 277736 89120 39617 138629 79208 198046 168490 198150 69308 158799 158423 247559 138697 99023 148541 29709 69312 138643 148518 89124 227759 79210 158441 128708 69318 316889 386291 59403 198035 29700 19812 277265 336...
result:
ok 100 lines
Test #15:
score: 4
Accepted
time: 136ms
memory: 10712kb
input:
75 80 50000 0 9926 9905 20094 30062 19980 30021 40295 40023 50352 50346 50081 59958 59979 70273 69708 70428 80155 80131 89517 90224 90104 99712 109557 120074 129322 119708 130717 139494 130135 139886 149735 140276 159688 169654 149442 170138 180614 189706 190267 189782 200369 200194 209632 219684 21...
output:
158427 39620 39605 198051 49520 277538 39604 9902 59412 69328 138642 9902 307113 69329 316883 168347 178244 158449 207961 188157 148668 118847 287170 29711 227906 158469 118840 297363 59412 287779 218167 89108 257880 79216 128724 198071 49516 168338 19800 119009 138630 89123 158446 208222 138646 138...
result:
ok 50000 lines
Test #16:
score: 4
Accepted
time: 139ms
memory: 10660kb
input:
75 80 50000 0 9959 10020 20140 20168 30201 40181 49885 39785 50085 50112 50061 60054 59754 69607 70278 69693 80490 90424 90194 100604 99674 109992 110396 119778 120018 119512 130210 130080 140120 149361 140330 150412 159300 150863 160759 159855 169162 169290 179081 179423 179095 190200 200875 199842...
output:
69309 128881 218168 128715 89117 79210 208042 198040 108916 59404 237645 198024 188122 247546 138849 49503 138814 198045 49509 217839 198038 79393 9902 217828 29709 49515 138624 29708 49516 29707 69316 188122 188125 89118 287148 69305 138627 257447 227741 39609 99005 79211 49503 168318 188136 297045...
result:
ok 50000 lines
Test #17:
score: 4
Accepted
time: 155ms
memory: 10900kb
input:
80 75 50000 0 9907 9924 20081 20135 29899 40045 30052 50304 40038 49940 59717 60359 70087 80345 80220 90322 89919 99460 100444 109416 109421 119386 119891 129477 140422 130427 139895 139570 149545 149952 160782 160917 159337 170181 169666 169243 180615 189300 179879 189878 199526 210801 209401 21898...
output:
218444 178744 109166 29746 99259 248143 238268 89357 69472 218439 297931 9903 89309 198524 29751 29734 208496 89350 198563 228295 59513 148914 297931 168804 317738 19815 69452 317805 218443 248286 198564 278001 208516 307834 158841 99242 129027 287930 49610 268098 59531 49605 79413 188599 59555 2481...
result:
ok 50000 lines
Test #18:
score: 4
Accepted
time: 145ms
memory: 10920kb
input:
75 80 100000 0 9935 20109 29946 30037 29781 39747 50358 39736 59810 69955 49689 79966 60370 89733 90177 100389 100152 110279 120697 120165 130567 129917 139760 140193 150397 149500 149862 159605 160672 160024 170499 170084 170327 179670 189722 200742 209987 210912 219232 230453 239811 239553 239580 ...
output:
158844 168727 79338 188609 158845 357495 119097 208487 129065 168802 158823 228380 278020 69453 168786 49609 228353 208485 307732 228308 19800 109171 59537 317751 148936 119150 49609 29735 327682 89334 49587 29732 208523 148934 119110 89309 109211 109177 188668 39674 89313 129064 49590 178682 238281...
result:
ok 100000 lines
Test #19:
score: 4
Accepted
time: 161ms
memory: 10884kb
input:
80 75 100000 0 10034 9901 9945 19878 30030 20104 30238 29886 39884 49930 60173 69851 60151 70229 80475 69755 89490 79741 100105 99814 110173 109508 110118 120358 119836 130395 140777 150412 160526 150840 159608 169951 169078 180066 180246 190857 190266 199060 200508 198975 209908 220039 230246 23072...
output:
317727 119111 99181 19804 138996 267900 19805 178580 158697 109182 277880 79323 59530 297894 59488 79336 238269 19800 69417 39692 218297 89287 99183 19817 29768 327706 99209 208405 138882 9901 228215 178697 49547 99261 178538 119017 69488 89291 357310 69466 89215 387145 49622 9906 139014 168665 9900...
result:
ok 100000 lines
Test #20:
score: 4
Accepted
time: 172ms
memory: 10948kb
input:
80 75 100000 0 10091 20104 9947 30079 39842 39746 50261 59656 59731 59675 69835 80396 70144 79592 89526 90081 89509 100025 99424 100547 109854 120111 110589 119284 130463 129299 130547 140266 140297 149827 150613 160228 160023 169664 170425 180198 179486 179554 190325 199129 211127 210690 219832 230...
output:
168348 89122 386176 217864 198041 208084 128801 326791 29708 89127 337138 118822 347010 108936 158432 79227 148531 59418 99022 59406 69311 376278 168338 128729 257443 247598 29713 128721 99082 79218 198045 228046 247569 227768 148533 267672 326790 128872 108935 267602 227763 396376 337300 9901 29713...
result:
ok 100000 lines
Test #21:
score: 4
Accepted
time: 182ms
memory: 11012kb
input:
80 80 100000 0 10099 19928 30018 39961 50010 49971 49878 60021 70147 60114 69924 80374 79616 80257 89591 89447 89511 100560 100115 110644 110388 119355 120710 119880 130623 130307 130617 139972 139940 149351 149814 159626 170457 169925 180559 180373 179360 189193 189412 200380 199647 200354 211130 2...
output:
39608 227749 148657 138620 297054 79215 108916 39608 198031 49510 59406 79283 39610 207965 29721 297268 59405 99014 49506 178238 198100 257444 188129 39603 148522 19806 306951 217851 347097 138623 89155 99017 188133 29705 158425 237658 108918 218049 138625 168339 118856 29710 178246 49505 148536 237...
result:
ok 100000 lines
Test #22:
score: 4
Accepted
time: 321ms
memory: 10940kb
input:
80 80 200000 0 10041 20046 19832 19961 29904 30205 39970 39719 49873 59827 69859 60005 69876 79913 80342 90165 90175 99503 110244 110196 109463 120678 120719 130458 129684 139842 139394 139906 150621 149840 159360 160514 160306 170704 169221 179449 179936 179231 190330 189369 189552 199169 199705 19...
output:
99275 59526 278010 138992 307788 59496 69369 69455 119076 208394 29740 99191 287963 267921 129004 119052 69480 198552 228183 39670 178601 49566 138980 138877 99210 19801 218337 188633 367310 109185 79328 29727 228238 248204 228389 337450 119061 129060 317632 168652 198481 218295 168785 19803 59532 2...
result:
ok 200000 lines
Test #23:
score: 4
Accepted
time: 196ms
memory: 11144kb
input:
80 80 200000 0 10071 19909 30239 19832 40030 30228 50267 40119 39964 49948 49716 60243 59838 70438 69528 69984 80106 90432 99513 110096 110396 119478 120479 129507 129728 129903 140343 140350 149444 150071 149951 160892 159182 170647 169735 170740 179941 179539 180310 189785 189333 199105 211070 209...
output:
29762 69450 347583 317711 208454 228272 188649 158862 89304 79360 278030 327610 69474 248218 99278 129058 29753 188658 69471 29742 109214 208460 248245 178704 178732 59493 39646 347438 129049 129055 178737 168793 307744 79396 268089 168753 268122 119118 148901 228368 49609 9900 79421 297977 198519 2...
result:
ok 200000 lines
Test #24:
score: 4
Accepted
time: 224ms
memory: 10960kb
input:
80 80 200000 0 10052 9979 20015 19833 20005 29915 29865 30020 39971 39944 50057 50268 60263 60196 59591 69729 69944 79927 80246 79799 90533 100324 90566 110391 100423 110282 120296 120424 130470 130229 129922 140130 139206 149831 159568 170587 169929 169088 179076 180862 180364 191001 189502 190313 ...
output:
178230 297100 138621 297109 198043 59411 336776 158437 178238 59414 108917 227797 79250 148529 237712 29703 89142 59407 327224 49505 79214 207930 69313 118830 49524 99019 237664 188139 198041 39608 19812 59411 118820 158440 99018 108916 238062 108921 287162 19800 178365 386176 227881 148522 287183 1...
result:
ok 200000 lines
Test #25:
score: 4
Accepted
time: 224ms
memory: 10964kb
input:
80 80 200000 0 9985 20092 20145 30116 30188 39848 50080 40288 59959 69586 79914 90117 79809 99468 90333 89911 99929 110441 99570 110656 119607 119275 120405 129697 129713 140204 149278 159701 149861 159362 170111 180013 169729 191009 189356 180584 199881 210281 220506 230870 219512 230432 240303 249...
output:
69319 108915 227748 9901 99021 148541 178225 247921 336656 29702 207932 198041 89119 188127 307291 257442 108918 118819 316986 138620 198028 118885 118814 207934 49569 138626 247545 366611 79222 89116 99018 128732 29704 138620 118817 118826 128732 306950 316856 89112 208221 69317 59414 218018 217844...
result:
ok 200000 lines