Submission #352094


Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }

    Scanner cin;

    long mod = (int)1e9 + 7;
    void calc()
    {
        cin = new Scanner();

        int N = cin.nextInt();
        int M = cin.nextInt();

        int[] A = new int[M];
        int[] B = new int[M];
        int[] C = new int[M];

        for (int i = 0; i < M; i++)
        {
            A[i] = cin.nextInt() - 1;
            B[i] = cin.nextInt() - 1;
            C[i] = cin.nextInt();
        }

        int K = cin.nextInt();

        int[] X = new int[K];
        int[] Y = new int[K];
        int[] Z = new int[K];

        for (int i = 0; i < K; i++)
        {
            X[i] = cin.nextInt() - 1;
            Y[i] = cin.nextInt() - 1;
            Z[i] = cin.nextInt();
        }

        int MAX = int.MaxValue / 3;
        int[,] dist = new int[N, N];
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                dist[i, j] = MAX;
            }
            dist[i, i] = 0;
        }

        for (int i = 0; i < M; i++)
        {
            dist[A[i], B[i]] = Math.Min(dist[A[i], B[i]], C[i]);
            dist[B[i], A[i]] = dist[A[i], B[i]];
        }

        for (int k = 0; k < N; k++)
        {
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    dist[i, j] = Math.Min(dist[i, j],
                        dist[i, k] + dist[k, j]);
                }
            }
        }

        for (int t = 0; t < K; t++)
        {
            int x = X[t];
            int y = Y[t];
            int z = Z[t];
            dist[x, y] = Math.Min(dist[x, y], z);
            dist[y, x] = dist[x, y];

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    dist[i, j] = Math.Min(dist[i, j]
                        ,Math.Min(dist[i, x] + dist[y, j]+ z
                        , dist[i, y] + dist[x, j] + z));
                }
            }

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    dist[j, i] = dist[i, j];
                }
            }

            long ret = 0;
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < i; j++)
                {
                    ret += dist[i, j];
                }
            }
            Console.WriteLine(ret);
        }

    }
}




class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}


class XRand
{
    uint x, y, z, w;


    public XRand()
    {
        init();
    }

    public XRand(uint s)
    {
        init();
        init_xor128(s);
    }

    void init()
    {
        x = 314159265; y = 358979323; z = 846264338; w = 327950288;

    }

    public void init_xor128(uint s)
    {
        z ^= s;
        z ^= z >> 21; z ^= z << 35; z ^= z >> 4;
        z *= 736338717;
    }

    uint next()
    {
        uint t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8;
    }

    public long nextLong(long m)
    {
        return (long)((((ulong)next() << 32) + next()) % (ulong)m);
    }

    public int nextInt(int m)
    {
        return (int)(next() % m);
    }

    public long nextLong(long min, long max)
    {
        return min + nextLong(max - min + 1);
    }

    public int nextInt(int min, int max)
    {
        return min + nextInt(max - min + 1);
    }

    public int nextIntP(int a)
    {
        return (int)Math.Pow(a, nextDouble());
    }

    public int nextIntP(int min, int max)
    {
        int diff = max - min;
        return min + nextIntP(diff + 2) - 1;
    }

    public long nextLongP(long a)
    {
        return (long)Math.Pow(a, nextDouble());
    }

    public long nextLongP(long min, long max)
    {
        long diff = max - min;
        return min + nextLongP(diff + 2) - 1;
    }


    public double nextDouble()
    {
        return (double)next() / uint.MaxValue;
    }

    public double nextDoubleP(double a)
    {
        return Math.Pow(a, nextDouble());
    }
}

Submission Info

Submission Time
Task C - アットコーダー王国の交通事情
User chokudai
Language C# (Mono 3.2.1.0)
Score 0
Code Size 5141 Byte
Status TLE
Exec Time 2037 ms
Memory 9548 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 10 0 / 90
Status
AC × 2
AC × 9
TLE × 22
AC × 9
TLE × 22
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
Subtask1 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 121 ms 8872 KB
subtask0_sample_02.txt AC 122 ms 8840 KB
subtask1_01.txt AC 124 ms 8968 KB
subtask1_02.txt TLE 2035 ms 9392 KB
subtask1_03.txt TLE 2035 ms 9272 KB
subtask1_04.txt TLE 2035 ms 9528 KB
subtask1_05.txt TLE 2034 ms 9544 KB
subtask1_06.txt TLE 2036 ms 9536 KB
subtask1_07.txt TLE 2035 ms 9548 KB
subtask1_08.txt TLE 2037 ms 9536 KB
subtask1_09.txt TLE 2034 ms 9536 KB
subtask1_10.txt TLE 2035 ms 9488 KB
subtask1_11.txt TLE 2036 ms 9532 KB
subtask1_12.txt TLE 2035 ms 9548 KB
subtask1_13.txt TLE 2036 ms 9544 KB
subtask1_14.txt TLE 2035 ms 9536 KB
subtask1_15.txt TLE 2036 ms 9536 KB
subtask1_16.txt TLE 2034 ms 9540 KB
subtask1_17.txt TLE 2036 ms 9528 KB
subtask1_18.txt TLE 2035 ms 9536 KB
subtask1_19.txt TLE 2035 ms 9492 KB
subtask1_20.txt TLE 2035 ms 9536 KB
subtask1_21.txt TLE 2035 ms 9532 KB
subtask1_22.txt TLE 2037 ms 9520 KB
subtask1_23.txt TLE 2036 ms 9536 KB
subtask1_24.txt AC 141 ms 9120 KB
subtask1_25.txt AC 137 ms 9132 KB
subtask1_26.txt AC 138 ms 9124 KB
subtask1_27.txt AC 139 ms 9132 KB
subtask1_28.txt AC 143 ms 9120 KB
subtask1_29.txt AC 122 ms 8992 KB