提出 #67953423

ソースコード 拡げる

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
const int maxn = 505;
const long long p = 998244353;
long long dis[maxn][maxn];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    int a, b;
    long long c;
    for (int i = 1; i <= n + 1; i++)
    {
        for (int j = 1; j <= n + 1; j++)
        {
            if (i != j)
                dis[i][j] = 1e18;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        dis[a][b] = dis[b][a] = min(dis[a][b], c);
    }
    int k;
    long long t;
    cin >> k >> t;
    for (int i = 1; i <= k; i++)
    {
        int now;
        cin >> now;
        dis[now][n + 1] = t;
        dis[n + 1][now] = 0;
    }
    for (int k = 1; k <= n + 1; k++)
    {
        for (int i = 1; i <= n + 1; i++)
            for (int j = 1; j <= n + 1; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    }
    int q;
    cin >> q;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (dis[i][j] < 1e18)
                ans += dis[i][j];
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, y;
            long long t;
            cin >> x >> y >> t;
            if (dis[x][y] > t)
            {
                if (dis[x][y] != 1e18)
                    ans -= dis[x][y] * 2;
                dis[x][y] = dis[y][x]=t;
                ans += 2 * t;
                for (int i = 1; i <= n + 1; i++)
                {
                    for (int j = 1; j <= n + 1; j++)
                    {
                        long long nxt=min(dis[i][x]+dis[y][j]+t,dis[i][y]+dis[x][j]+t);
                        if (dis[i][j] > nxt)
                        {
                            if (i != n + 1 && j != n + 1 && dis[i][j] != 1e18)
                                ans -= dis[i][j];
                            dis[i][j] =nxt;
                            if (i != n + 1 && j != n + 1)
                                ans += dis[i][j];
                        }
                    }
                }
            }
        }
        else if (op == 2)
        {
            int x;
            cin >> x;
            dis[x][n + 1] = t;
            dis[n + 1][x] = 0;
            for (int i = 1; i <= n + 1; i++)
            {
                for (int j = 1; j <= n + 1; j++)
                {
                    long long nxt=min(dis[i][x]+dis[n+1][j]+t,dis[i][n+1]+dis[x][j]);
                    if (dis[i][j] > nxt)
                    {
                        if (i != n + 1 && j != n + 1 && dis[i][j] != 1e18)
                            ans -= dis[i][j];
                        dis[i][j] = nxt;
                        if (i != n + 1 && j != n + 1)
                            ans += dis[i][j];
                    }

                }
            }
        }
        else
            cout << ans << '\n';
    }
}

提出情報

提出日時
問題 E - Development
ユーザ Alliy666
言語 C++ 23 (gcc 12.2)
得点 450
コード長 3176 Byte
結果 AC
実行時間 247 ms
メモリ 5620 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 450 / 450
結果
AC × 1
AC × 29
セット名 テストケース
Sample sample_01.txt
All hand.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, sample_01.txt
ケース名 結果 実行時間 メモリ
hand.txt AC 1 ms 3436 KiB
random_01.txt AC 228 ms 5420 KiB
random_02.txt AC 45 ms 4440 KiB
random_03.txt AC 218 ms 5620 KiB
random_04.txt AC 166 ms 5200 KiB
random_05.txt AC 226 ms 5432 KiB
random_06.txt AC 50 ms 4544 KiB
random_07.txt AC 205 ms 5472 KiB
random_08.txt AC 188 ms 5564 KiB
random_09.txt AC 212 ms 5488 KiB
random_10.txt AC 50 ms 4652 KiB
random_11.txt AC 188 ms 5396 KiB
random_12.txt AC 90 ms 4972 KiB
random_13.txt AC 164 ms 5620 KiB
random_14.txt AC 33 ms 4560 KiB
random_15.txt AC 187 ms 5392 KiB
random_16.txt AC 100 ms 5084 KiB
random_17.txt AC 150 ms 5488 KiB
random_18.txt AC 102 ms 5188 KiB
random_19.txt AC 178 ms 5540 KiB
random_20.txt AC 129 ms 5168 KiB
random_21.txt AC 34 ms 4696 KiB
random_22.txt AC 75 ms 4772 KiB
random_23.txt AC 80 ms 4816 KiB
random_24.txt AC 84 ms 4956 KiB
random_25.txt AC 215 ms 5456 KiB
random_26.txt AC 205 ms 5552 KiB
random_27.txt AC 247 ms 5488 KiB
sample_01.txt AC 1 ms 3500 KiB