제출 #445380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445380		armaho	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	788 ms	27048 KiB

commuter_pass

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <bitset>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <list>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <math.h>

using namespace std;

template <typename input_type>
inline input_type input() {
    input_type inp;
    cin >> inp;

    return inp;
}

const int max_sz = 1e5 + 5;
const long long inf = 1e18;

long long ans[max_sz], dist[3][max_sz];
pair <int, int> sz, pnt, goal;
pair <long long, long long> dp[max_sz];
vector <int> dag, upd[max_sz];
vector <pair <int, int>> graph[max_sz];

void Dijkstra(int root, int idx) {
    set <pair <long long, int>> vrtx_lst;
    for (int i = 0; i < sz.first; i++) {
        dist[idx][i] = (i == root) ? 0 : inf;
        vrtx_lst.insert({dist[idx][i], i});
    }

    while (not vrtx_lst.empty()) {
        int vrtx = (*vrtx_lst.begin()).second;
        vrtx_lst.erase(vrtx_lst.begin());

        for (auto ngh : graph[vrtx]) {
            if (dist[idx][ngh.first] > dist[idx][vrtx] + ngh.second) {
                vrtx_lst.erase({dist[idx][ngh.first], ngh.first});
                dist[idx][ngh.first] = dist[idx][vrtx] + ngh.second, vrtx_lst.insert({dist[idx][ngh.first], ngh.first});
            }
        }

        if (not idx) {
            dag.push_back(vrtx);
        }
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

    sz = {input<int>(), input<int>()}, pnt = {input<int>() - 1, input<int>() - 1}, goal = {input<int>() - 1, input<int>() - 1};
    for (int i = 0; i < sz.second; i++) {
        pair <int, int> endpnt = {input<int>() - 1, input<int>() - 1};
        int wght = input<int>();

        graph[endpnt.first].push_back({endpnt.second, wght}), graph[endpnt.second].push_back({endpnt.first, wght});
    }

    Dijkstra(pnt.first, 0), Dijkstra(goal.first, 1), Dijkstra(goal.second, 2);
    for (int i = 0; i < sz.first; i++) {
        for (auto ngh : graph[i]) {
            if (dist[0][i] == dist[0][ngh.first] + ngh.second) {
                upd[i].push_back(ngh.first);
            }
        }
    }

    for (auto vrtx : dag) {
        ans[vrtx] = dist[1][vrtx] + dist[2][vrtx], dp[vrtx] = {dist[1][vrtx], dist[2][vrtx]};

        for (auto par : upd[vrtx]) {
            dp[vrtx] = {min(dp[vrtx].first, dp[par].first), min(dp[vrtx].second, dp[par].second)};
            ans[vrtx] = min(ans[vrtx], ans[par]);
        }

        ans[vrtx] = min(ans[vrtx], min(dist[2][vrtx] + dp[vrtx].first, dist[1][vrtx] + dp[vrtx].second));
    }

    cout << min(ans[pnt.second], dist[1][goal.second]);
    return 0;
}

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