XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#88952 #1388. 莉可莉丝 Wrong Answer 20 432 ms 94332 K C++ 17 / 1.7 K Fearr 2023-05-16 18:17:33
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define eps 1e-6
//#define int long long
const ll N = 2005;
struct node {
    int v, w;
};
vector<node> e[N];
ll d[N][N][3];
int in[N], deg[N], n;
void topo(int x) {
    for (int i = 1; i <= n; ++i) deg[i] = in[i];
    queue<int> q;
    q.push(x);
    d[x][x][1] = d[x][x][2] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < e[u].size(); ++i) {
            int v = e[u][i].v;
            ll to = e[u][i].w + d[x][u][1];
            if (to < d[x][v][1]) {
                if (d[x][v][1] != 1e10)
                    d[x][v][2] = min(d[x][v][2], d[x][v][1]);
                d[x][v][1] = to;
            } else {
                d[x][v][2] = min(d[x][v][2], to);
            }
            deg[v]--;
            if (!deg[v])
                q.push(v);
        }
    }
}
signed main() {
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back(node{ v, w });
        in[v]++;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) d[i][j][1] = d[i][j][2] = 1e10;
    for (int i = 1; i <= n; ++i) topo(i);
    ll ans = 1e15;
    for (int i = 1; i <= n - 1; ++i)
        for (int j = i + 1; j <= n; ++j) {
            if (ans > d[1][i][1] + d[i][j][1] + d[i][j][2] + d[j][n][1]) {
                ans = d[1][i][1] + d[i][j][1] + d[i][j][2] + d[j][n][1];
                //			cout << "i: " << i << "j: " << j << '\n';
            }
            // ans = min(ans, d[1][i][1] + d[i][j][1] + d[i][j][2] + d[j][n][1]);
        }
    cout << ans << '\n';
    /*for (int i = 5; i <= 5; ++i)
            for (int j = 1; j <= n; ++j) {
                    cout << d[i][j][1] << ' ' << d[i][j][2] << '\n';

            }*/
    return 0;
}
子任务 #1
Wrong Answer
得分：20
测试点 #1
Accepted
得分：100
用时：3 ms
内存：384 KiB

输入文件（01.in） 

4 4
1 2 5
1 3 7
2 4 6
3 4 8

答案文件（01.ans） 

26

用户输出 

26

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：5 ms
内存：384 KiB

输入文件（02.in） 

5 10
1 2 1
1 3 3
3 4 9
2 5 1
1 5 10
4 5 2
2 3 9
3 5 3
1 4 4
2 4 7

答案文件（02.ans） 

8

用户输出 

8

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：5 ms
内存：492 KiB

输入文件（03.in） 

9 10
1 2 1
2 3 1
3 4 1
4 9 1
1 5 2
5 8 1
5 6 1
6 7 1
8 7 2
7 9 1

答案文件（03.ans） 

8

用户输出 

8

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：4 ms
内存：576 KiB

输入文件（04.in） 

50 100
1 2 331
2 3 423
3 4 831
3 5 196
2 6 467
4 7 841
5 8 589
6 9 930
9 10 481
3 11 293
7 12 968
5 
<852 bytes omitted>

答案文件（04.ans） 

4204

用户输出 

4204

系统信息 

Exited with return code 0
测试点 #5
Wrong Answer
得分：0
用时：4 ms
内存：620 KiB

输入文件（05.in） 

50 100
1 2 37
2 3 90
3 4 270
1 5 616
4 6 462
6 7 801
5 8 922
8 9 701
5 10 204
7 11 330
1 12 588
6 13
<840 bytes omitted>

答案文件（05.ans） 

1685

用户输出 

2002

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #6
Wrong Answer
得分：0
用时：14 ms
内存：25220 KiB

输入文件（06.in） 

942 9498
1 2 87293
1 3 92214
3 4 20834
3 5 924
4 6 71171
6 7 66669
6 8 57264
6 9 98803
5 10 52661
7 
<129920 bytes omitted>

答案文件（06.ans） 

214920

用户输出 

381795

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #7
Wrong Answer
得分：0
用时：16 ms
内存：25884 KiB

输入文件（07.in） 

954 9620
1 2 48928
1 3 77602
2 4 9736
2 5 82149
1 6 14100
2 7 73201
7 8 31260
7 9 82801
2 10 69933
6
<131587 bytes omitted>

答案文件（07.ans） 

184919

用户输出 

348197

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #8
Wrong Answer
得分：0
用时：16 ms
内存：25356 KiB

输入文件（08.in） 

946 9136
1 2 3322
1 3 76072
1 4 16527
2 5 9562
5 6 60762
6 7 67224
1 8 88909
7 9 91358
9 10 25363
4 
<124859 bytes omitted>

答案文件（08.ans） 

191259

用户输出 

366127

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #9
Wrong Answer
得分：0
用时：17 ms
内存：26188 KiB

输入文件（09.in） 

963 9814
1 2 14048
2 3 40980
2 4 76354
1 5 32242
5 6 57710
4 7 74690
3 8 696
2 9 93547
5 10 83686
3 
<134310 bytes omitted>

答案文件（09.ans） 

191404

用户输出 

383010

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #10
Wrong Answer
得分：0
用时：15 ms
内存：23408 KiB

输入文件（10.in） 

907 9592
1 2 56498
2 3 39992
1 4 97777
3 5 43535
1 6 60669
3 7 8684
6 8 8342
5 9 3341
5 10 54069
3 1
<131170 bytes omitted>

答案文件（10.ans） 

159164

用户输出 

281309

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #11
Wrong Answer
得分：0
用时：17 ms
内存：26096 KiB

输入文件（11.in） 

961 9738
1 2 77603
1 3 55107
2 4 94838
1 5 86873
2 6 71895
4 7 42417
7 8 18633
3 9 50720
2 10 8124
2
<133328 bytes omitted>

答案文件（11.ans） 

226759

用户输出 

421551

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #12
Wrong Answer
得分：0
用时：16 ms
内存：24176 KiB

输入文件（12.in） 

922 9495
1 2 74386
1 3 46842
1 4 45986
3 5 28221
4 6 813
6 7 9673
5 8 84925
5 9 27070
1 10 28158
6 1
<129894 bytes omitted>

答案文件（12.ans） 

206120

用户输出 

390540

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #13
Wrong Answer
得分：0
用时：14 ms
内存：26496 KiB

输入文件（13.in） 

969 9940
1 2 52898
2 3 66949
1 4 33891
1 5 89883
3 6 58933
1 7 43115
6 8 705
1 9 11964
2 10 27082
7 
<136015 bytes omitted>

答案文件（13.ans） 

180825

用户输出 

347571

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #14
Wrong Answer
得分：0
用时：16 ms
内存：25860 KiB

输入文件（14.in） 

958 9208
1 2 6355
1 3 33442
3 4 5708
1 5 82239
5 6 54649
4 7 90055
1 8 96152
8 9 66805
3 10 2693
9 1
<125934 bytes omitted>

答案文件（14.ans） 

201075

用户输出 

388084

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #15
Wrong Answer
得分：0
用时：49 ms
内存：93672 KiB

输入文件（15.in） 

1978 9706
1 2 78441
1 3 93204
1 4 34169
4 5 68390
4 6 68610
2 7 4971
2 8 48605
8 9 41970
4 10 67572

<143038 bytes omitted>

答案文件（15.ans） 

235715

用户输出 

300743

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #16
Wrong Answer
得分：0
用时：45 ms
内存：94084 KiB

输入文件（16.in） 

1988 9915
1 2 18876
2 3 50319
2 4 23783
3 5 12278
5 6 52624
2 7 94109
6 8 45323
7 9 85178
3 10 40196
<146223 bytes omitted>

答案文件（16.ans） 

180635

用户输出 

214555

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #17
Wrong Answer
得分：0
用时：46 ms
内存：94332 KiB

输入文件（17.in） 

1992 9832
1 2 8550
2 3 74022
2 4 32107
2 5 35012
1 6 63629
4 7 68299
4 8 32176
2 9 52376
7 10 37712

<145210 bytes omitted>

答案文件（17.ans） 

400566

用户输出 

555420

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #18
Wrong Answer
得分：0
用时：44 ms
内存：90200 KiB

输入文件（18.in） 

1904 9599
1 2 38275
1 3 8569
2 4 22406
4 5 52940
5 6 90205
4 7 65298
7 8 98943
5 9 69325
6 10 47027

<141327 bytes omitted>

答案文件（18.ans） 

553323

用户输出 

1067022

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #19
Wrong Answer
得分：0
用时：41 ms
内存：93056 KiB

输入文件（19.in） 

1966 9554
1 2 17891
2 3 8060
3 4 6259
1 5 33026
5 6 71923
6 7 60286
6 8 54211
4 9 29160
9 10 31533
4
<141078 bytes omitted>

答案文件（19.ans） 

893510

用户输出 

1741965

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
测试点 #20
Wrong Answer
得分：0
用时：45 ms
内存：92864 KiB

输入文件（20.in） 

1963 9921
1 2 35364
2 3 2654
1 4 37531
1 5 42140
5 6 96240
2 7 28727
6 8 73712
8 9 35997
4 10 96140

<146347 bytes omitted>

答案文件（20.ans） 

843364

用户输出 

1638287

Special Judge 信息 

Files user_out and answer differ

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ.