Submission #67966327

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<long long>> dis(n + 1, vector<long long>(n + 1, inf));
    for (int i = 1; i <= n; ++i) {
        dis[i][i] = 0;
    }
    
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        if (dis[u][v] > c) {
            dis[u][v] = c;
            dis[v][u] = c;
        }
    }
    
    int k, t;
    cin >> k >> t;
    vector<int> airports(k);
    for (int i = 0; i < k; ++i) {
        cin >> airports[i];
    }
    
    // Update distances between airports
    for (int u : airports) {
        for (int v : airports) {
            if (dis[u][v] > t) {
                dis[u][v] = t;
                dis[v][u] = t;
            }
        }
    }
    
    // Floyd-Warshall algorithm
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dis[i][k] != inf && dis[k][j] != inf) {
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
    }
    
    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x, y, t;
            cin >> x >> y >> t;
            if (dis[x][y] > t) {
                dis[x][y] = t;
                dis[y][x] = t;
                // Update all pairs using Floyd-Warshall
                for (int i = 1; i <= n; ++i) {
                    for (int j = 1; j <= n; ++j) {
                        if (dis[i][x] != inf && dis[y][j] != inf) {
                            dis[i][j] = min(dis[i][j], dis[i][x] + t + dis[y][j]);
                        }
                        if (dis[i][y] != inf && dis[x][j] != inf) {
                            dis[i][j] = min(dis[i][j], dis[i][y] + t + dis[x][j]);
                        }
                    }
                }
            }
        } else if (type == 2) {
            int x;
            cin >> x;
            airports.push_back(x);
            // Update distances between the new airport and existing airports
            for (int u : airports) {
                if (dis[u][x] > t) {
                    dis[u][x] = t;
                    dis[x][u] = t;
                    // Update all pairs using Floyd-Warshall
                    for (int i = 1; i <= n; ++i) {
                        for (int j = 1; j <= n; ++j) {
                            if (dis[i][u] != inf && dis[x][j] != inf) {
                                dis[i][j] = min(dis[i][j], dis[i][u] + t + dis[x][j]);
                            }
                            if (dis[i][x] != inf && dis[u][j] != inf) {
                                dis[i][j] = min(dis[i][j], dis[i][x] + t + dis[u][j]);
                            }
                        }
                    }
                }
            }
        } else if (type == 3) {
            long long total = 0;
            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= n; ++j) {
                    if (dis[i][j] != inf) {
                        total += dis[i][j];
                    }
                }
            }
            cout << total << "\n";
        }
    }
    
    return 0;
}

Submission Info

Submission Time
Task E - Development
User Sarthak_Borse
Language C++ 20 (gcc 12.2)
Score 0
Code Size 3412 Byte
Status TLE
Exec Time 3865 ms
Memory 5548 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 450
Status
AC × 1
AC × 19
TLE × 10
Set Name Test Cases
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
Case Name Status Exec Time Memory
hand.txt AC 1 ms 3564 KiB
random_01.txt AC 642 ms 5424 KiB
random_02.txt AC 168 ms 3968 KiB
random_03.txt TLE 3862 ms 5264 KiB
random_04.txt TLE 3862 ms 4832 KiB
random_05.txt AC 1149 ms 5464 KiB
random_06.txt AC 276 ms 4104 KiB
random_07.txt TLE 3862 ms 5244 KiB
random_08.txt TLE 3862 ms 5168 KiB
random_09.txt AC 1800 ms 5476 KiB
random_10.txt AC 447 ms 4096 KiB
random_11.txt TLE 3862 ms 5224 KiB
random_12.txt TLE 3862 ms 4404 KiB
random_13.txt AC 1625 ms 5480 KiB
random_14.txt AC 259 ms 4068 KiB
random_15.txt TLE 3862 ms 5188 KiB
random_16.txt TLE 3862 ms 4468 KiB
random_17.txt AC 2138 ms 5444 KiB
random_18.txt AC 1242 ms 4976 KiB
random_19.txt TLE 3865 ms 5232 KiB
random_20.txt TLE 3862 ms 4764 KiB
random_21.txt AC 143 ms 4268 KiB
random_22.txt AC 485 ms 4384 KiB
random_23.txt AC 135 ms 4524 KiB
random_24.txt AC 3234 ms 4352 KiB
random_25.txt AC 267 ms 5484 KiB
random_26.txt AC 2366 ms 5448 KiB
random_27.txt AC 730 ms 5548 KiB
sample_01.txt AC 1 ms 3472 KiB