Submission #684410

#	Time	Username	Problem	Language	Result	Execution time	Memory
684410		overwatch9	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	84 ms	1876 KiB

commuter_pass

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int MAX_N = 300 + 1;
vector <pair <int, int>> adj[MAX_N];
ll dis[MAX_N][MAX_N];
int N, M, S, T, U, V;
int main() {
    cin >> N >> M >> S >> T >> U >> V;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j)
                dis[i][i] = 0;
            else
                dis[i][j] = 1e15;
        }
    }
    for (int i = 0; i < M; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
        dis[a][b] = dis[b][a] = min(dis[a][b], (ll)w);
    }
    // for (int i = 1; i <= N; i++) {
    //     for (int j = 1; j <= N; j++) {
    //         cout << dis[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // cout << '\n';

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        }
    }
    
    // for (int i = 1; i <= N; i++) {
    //     for (int j = 1; j <= N; j++) {
    //         cout << dis[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // cout << '\n';

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                if (dis[S][i] + dis[i][j] + dis[j][T] == dis[S][T])
                    dis[i][j] = 0;
            }
        }
    }
    
    // for (int i = 1; i <= N; i++) {
    //     for (int j = 1; j <= N; j++) {
    //         cout << dis[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    cout << '\n';

    cout << dis[U][V] << '\n';
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45