QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#839680	#9903. 最短路径	kenkenken^#	0	13ms	28684kb	C++23	1.8kb	2025-01-02 00:47:40	2025-01-02 00:47:42

Judging History

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

[2025-01-02 00:47:42]
评测

测评结果：0
用时：13ms
内存：28684kb

查看

[2025-01-02 00:47:40]
提交

answer

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define pob pop_back
#define all(x) begin(x), end(x)
#define SZ(x) ssize(x)
using namespace std;

#ifdef LOCAL
#define HEHE freopen("in.txt", "r", stdin);
#define debug(HEHE...) cerr << #HEHE << " = ", dout(HEHE)
void dout() { cerr << "\n"; }
template<typename T, typename... U>
void dout(T t, U... u) { cerr << t << ' '; dout(u...); }
#else
#define HEHE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 7122
#endif

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)

#define chmax(a, b) a = (a) > (b) ? (a) : (b)
#define chmin(a, b) a = (a) < (b) ? (a) : (b)

#define int long long

const int inf = 1ll << 60;
int n, q;
vector<vector<int>> dis, pre[305], suf[305], ans[305];

signed main() {
    HEHE
    cin >> n >> q;
    dis.assign(n + 1, vector<int>(n + 1));
    pre[0].assign(n + 1, vector<int> (n + 1));
    FOR (i, 1, n) FOR (j, 1, n)
        cin >> dis[i][j];
    pre[0] = suf[n + 1] = dis;
    FOR (k, 1, n) {
        pre[k] = pre[k - 1];
        FOR (i, 1, n) FOR (j, 1, n) {
            chmin(pre[k][i][j], pre[k][i][k] + pre[k][k][j]);
        }
    }
    for (int k = n; k >= 1; k--) {
        suf[k] = suf[k + 1];
        FOR (i, 1, n) FOR (j, 1, n) {
            chmin(suf[k][i][j], suf[k][i][k] + suf[k][k][j]);
        }
    }
    FOR (k, 1, n) {
        auto dis1 = pre[k - 1];
        auto dis2 = suf[k + 1];
        FOR (i, 1, n) {
            dis1[i][k] = dis1[k][i] = inf;
            dis2[i][k] = dis2[k][i] = inf;
        }
        FOR (i, 1, n) {
            FOR (j, 1, n) {
                chmin(dis1[i][j], dis2[i][j]);
            }
        }
        ans[k] = dis1;
    }
    while (q--) {
        int s, t, p; cin >> s >> t >> p;
        cout << ans[p][s][t] << '\n';
    }
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 0

Wrong Answer

time: 12ms

memory: 28548kb

input:

100 100
0 7772271323914 22125803016911 3221373 4166251171807 748339783252 34065805188167 50811428832368 1367651438428 24197139580618 6663135541534 27879426632102 15365243414328 10780564011323 2018609024 397712557916 28396067120913 356407886112 44232262619414 162855983068 447276 67425790697675 173378...

output:

result:

wrong answer 1st numbers differ - expected: '65676043', found: '66780767'

Test #2:

score: 0

Wrong Answer

time: 13ms

memory: 28684kb

input:

100 100
0 17578387256913 79089544497 431 594034211131 5170073338267 19361776466479 4427688105 11926603171157 45072603252 11943768005878 50148978000869 106737346550 27519538966959 37137900185801 3989886236022 15439195175968 19533214331980 4915912422439 66000188414990 29166748845681 354388844 66952055...

output:

result:

wrong answer 1st numbers differ - expected: '270396', found: '13978568'

Test #3:

score: 0

Wrong Answer

time: 4ms

memory: 28552kb

input:

100 100
0 773801766444 3840925618 1343152952632 64307613436502 8683601469 45434524869106 81117353046 1987337565207 2858076509641 243425132692 1802644161264 25822170325295 6528483907 41283282749 3826491866697 22344866920790 96931641334570 5174664972951 1538931163479 47147864358837 51639382527727 9867...

output:

result:

wrong answer 1st numbers differ - expected: '2561993', found: '4622939'

Test #4:

score: 0

Memory Limit Exceeded

input:

300 1000
0 1395254281321 81149967048674 808789341190 79819267873907 57367221292974 13013648824390 64258407230458 14605579839044 12975220495832 120220182607 39743014887008 3266138366431 119198662688 28545770063374 17260222479825 21107475181134 55682577272703 13633518098188 40028750178497 550275401200...

output:

result:

Test #5:

score: 0

Memory Limit Exceeded

input:

300 1000
0 6409029058 18566975677517 1453118645319 19988064330 32639805173638 1639371569240 698806223545 185977936143 1082787768141 2239906104533 4403543180683 961039210337 4145037246 1858235 2692041139214 2307668378 1339668614 6253996882 17345652389482 1009665462517 17453151773298 3394297603587 135...

output:

result:

Test #6:

score: 0

Memory Limit Exceeded

input:

300 500000
0 87730664049 1603788381608 71952849510530 1142923985 24159738602021 92997246299231 64880292979225 50411033738604 54528465801 31135537246199 231468171471 419 236677264159 38114009155579 2508003778771 57570811058461 24329307886989 292160437 4902439019817 15740104936818 44927292337698 79204...

output:

result:

Test #7:

score: 0

Memory Limit Exceeded

input:

300 500000
0 52626347413773 1707334632128 70009373655708 25860849031824 32110463708287 3869001849431 346520043666 34919901831451 18512922395 14200680384312 436214584213 79240628473151 14981957306825 1273864589622 475718847939 5308515658147 30868844002 272698735884 23608283030932 509189357147 1289077...

output:

result:

Test #8:

score: 0

Memory Limit Exceeded

input:

300 500000
0 6330470680301 23874488164149 98626 4160170543478 91396404907 58736315444 12401313360570 14412917281027 38099628392841 282475659499 671873736937 772895099008 19153316198 7022869 27995285198114 11692649915256 7588637657572 823853943323 2206830727999 2151020585 915266887628 5916118204273 1...

output:

result:

Test #9:

score: 0

Memory Limit Exceeded

input:

300 500000
0 54720923847450 10903523785666 4358689132 83283776625462 8218771493732 35488829878660 3339439 6500864120913 61307902687569 53710291769435 19917041512 463251296446 6646718981507 2456241779832 481716427467 7469732375 21084043486 206425878 740838785326 11139961838828 136091417 806439547295 ...

output:

result:

Test #10:

score: 0

Memory Limit Exceeded

input:

300 500000
0 5722301682716 8452307607009 329027699594 1815251343 30089254283 943061127487 44841695197962 5020142381745 3623788938103 10069313592506 5560807810421 67387215059128 1502958639680 4306022199080 36093310364434 21620815132153 1864471728058 3394408494751 1018569343784 2241919490 118027786703...

output: