编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#88308 #1388. 莉可莉丝 Wrong Answer 10 2962 ms 19668 K Java / 2.7 K nafnil 2023-05-08 15:30:58
显示原始代码
import java.io.*;
import java.util.*;

public class Main {
    public static Reader in;
    public static PrintWriter out;
    public static void main(String[] args) {
        out = new PrintWriter(new BufferedOutputStream(System.out));
        in = new Reader();
        int t = 1;
        while (t-- > 0) solve();
        out.close();
    }

    static Map<Integer, int[]> cache;
    static List<int[]>[] lists;
    static void solve() {
        int n = in.nextInt(), m = in.nextInt();
        cache = new HashMap<>();
        lists = new ArrayList[n + 1];
        cache.put(1, new int[] { 0, 0x3f3f3f3f });
        Arrays.setAll(lists, a -> new ArrayList<>());
        for (int i = 0; i < m; i++) {
            int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
            lists[b].add(new int[] { a, c });
        }
        int[] dfs = dfs(n);
        out.println(dfs[1]);
    }

    static int[] dfs(int x) {
        if (cache.containsKey(x))
            return cache.get(x);
        int[] re = new int[] { 0x3f3f3f3f, 0x3f3f3f3f };
        for (int[] pre : lists[x]) {
            int[] dfs = dfs(pre[0]);
            re[1] = Math.min(re[1], pre[1] + Math.min(dfs[1], dfs[0] + re[0]));
            re[0] = Math.min(re[0], dfs[0] + pre[1]);
        }
        cache.put(x, re);
        return re;
    }

    static int qmi(long a, int b, int p) {
        long ans = 1;
        a = (a % p + p) % p;
        for (; b > 0; b >>= 1) {
            if ((b & 1) != 0)
                ans = (a * ans) % p;
            a = (a * a) % p;
        }
        return (int) ans;
    }

    static class Reader {
        private BufferedReader br;
        private StringTokenizer st;

        Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            try {
                while (st == null || !st.hasMoreTokens()) {
                    st = new StringTokenizer(br.readLine());
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) arr[i] = nextInt();
            return arr;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }
    }
}
子任务 #1
Wrong Answer
得分:10
测试点 #1
Accepted
得分:100
用时:66 ms
内存:11860 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
用时:69 ms
内存:12100 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
Wrong Answer
得分:0
用时:67 ms
内存:11808 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

用户输出

9

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #4
Wrong Answer
得分:0
用时:73 ms
内存:11896 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

用户输出

4958

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #5
Wrong Answer
得分:0
用时:78 ms
内存:11968 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

用户输出

1722

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #6
Wrong Answer
得分:0
用时:178 ms
内存:17680 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

用户输出

225860

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #7
Wrong Answer
得分:0
用时:140 ms
内存:16212 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

用户输出

213464

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #8
Wrong Answer
得分:0
用时:157 ms
内存:17772 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

用户输出

208100

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #9
Wrong Answer
得分:0
用时:173 ms
内存:18272 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

用户输出

213832

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #10
Wrong Answer
得分:0
用时:165 ms
内存:17244 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

用户输出

192083

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #11
Wrong Answer
得分:0
用时:175 ms
内存:17956 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

用户输出

297292

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #12
Wrong Answer
得分:0
用时:178 ms
内存:18632 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

用户输出

218412

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #13
Wrong Answer
得分:0
用时:169 ms
内存:17468 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

用户输出

210333

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #14
Wrong Answer
得分:0
用时:168 ms
内存:17488 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

用户输出

238837

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #15
Wrong Answer
得分:0
用时:199 ms
内存:19668 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

用户输出

270232

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #16
Wrong Answer
得分:0
用时:183 ms
内存:17540 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

用户输出

180962

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #17
Wrong Answer
得分:0
用时:161 ms
内存:18284 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

用户输出

415874

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #18
Wrong Answer
得分:0
用时:182 ms
内存:18088 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

用户输出

594999

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #19
Wrong Answer
得分:0
用时:200 ms
内存:19340 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

用户输出

927386

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0
测试点 #20
Wrong Answer
得分:0
用时:181 ms
内存:17912 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

用户输出

860432

Special Judge 信息

Files user_out and answer differ

系统信息

Exited with return code 0