제출 #595058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
595058		Vanilla	Commuter Pass (JOI18_commuter_pass)	C++17	24 / 100	86 ms	3116 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 302;
vector <pair <int, int> > ad [maxn];
int64 d [maxn][maxn];

int main() {
    int n,m, s1, t1, s2, t2;
    cin >> n >> m >> s1 >> t1 >> s2 >> t2;
    for (int i = 0; i < maxn; i++) for (int j = 0; j < maxn; j++) d[i][j] = 1e18;
    for (int i = 0; i < m; i++){
        int x,y,c;
        cin >> x >> y >> c;
        ad[x].push_back({y, c});
        ad[y].push_back({x, c});
    }
    auto dijkstra = [&] (int start) {
        set <pair <int64, int> > s;
        d[start][start] = 0;
        s.insert({0, start});
        while (!s.empty()) {
            int u = s.begin()->second;
            s.erase(s.begin());
            for (auto &[v, cost]: ad[u]) {
                if (d[start][u] + cost < d[start][v]) {
                    s.erase({d[start][v], v});
                    d[start][v] = d[start][u] + cost;
                    s.insert({d[start][v], v});
                }
            }
        }
    };
    for (int i = 1; i <= n; i++){
        dijkstra(i);
    }
    int64 rs = d[s2][t2];
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            if (min(d[s1][i] + d[t1][j], d[t1][i] + d[s1][j]) + d[i][j] == d[s1][t1]) {
                rs = min(rs, min(d[t2][i] + d[s2][j], d[s2][i] + d[t2][j]));
            }
        }
    }
    cout << rs << "\n";
    return 0;
}

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