結果

問題 No.614 壊れたキャンパス
ユーザー MisterMister
提出日時 2020-08-18 20:48:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,770 ms / 2,000 ms
コード長 3,397 bytes
コンパイル時間 1,799 ms
コンパイル使用メモリ 128,524 KB
実行使用メモリ 78,676 KB
最終ジャッジ日時 2024-10-12 03:13:05
合計ジャッジ時間 18,662 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 1 ms
6,820 KB
testcase_08 AC 1,228 ms
74,916 KB
testcase_09 AC 989 ms
74,048 KB
testcase_10 AC 1,494 ms
78,676 KB
testcase_11 AC 1,581 ms
75,372 KB
testcase_12 AC 1,499 ms
75,420 KB
testcase_13 AC 1,543 ms
75,916 KB
testcase_14 AC 1,770 ms
77,188 KB
testcase_15 AC 1,232 ms
76,692 KB
testcase_16 AC 1,382 ms
75,144 KB
testcase_17 AC 1,456 ms
73,752 KB
testcase_18 AC 477 ms
62,956 KB
testcase_19 AC 439 ms
60,600 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <tuple>
#include <limits>

template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T>
std::map<T, int> compress(std::vector<T>& v) {
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());

    std::map<T, int> rev;
    for (int i = 0; i < (int)v.size(); ++i) rev[v[i]] = i;
    return rev;
}

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
struct Graph {
    std::vector<std::vector<Edge<Cost>>> graph;

    Graph(int n = 0) : graph(n) {}

    void span(bool direct, int src, int dst, Cost cost = 1) {
        graph[src].emplace_back(src, dst, cost);
        if (!direct) graph[dst].emplace_back(dst, src, cost);
    }

    int size() const { return graph.size(); }
    void clear() { graph.clear(); }
    void resize(int n) { graph.resize(n); }

    std::vector<Edge<Cost>>& operator[](int v) { return graph[v]; }
    std::vector<Edge<Cost>> operator[](int v) const { return graph[v]; }
};

template <class Cost>
std::vector<Cost> dijkstra(const Graph<Cost>& graph, int s) {
    std::vector<Cost> dist(graph.size(), -1);
    dist[s] = 0;
    MinHeap<std::pair<Cost, int>> que;
    que.emplace(0, s);

    while (!que.empty()) {
        int v;
        Cost d;
        std::tie(d, v) = que.top();
        que.pop();
        if (d > dist[v]) continue;

        for (const auto& e : graph[v]) {
            if (dist[e.dst] != -1 &&
                dist[e.dst] <= dist[v] + e.cost) continue;
            dist[e.dst] = dist[v] + e.cost;
            que.emplace(dist[e.dst], e.dst);
        }
    }

    return dist;
}

using lint = long long;

void solve() {
    int n, m, k, s, t;
    std::cin >> n >> m >> k >> s >> t;
    --s, --t;

    auto enc = [&](int x, int y) { return x + lint(y) * n; };

    std::vector<std::pair<lint, lint>> es;
    std::vector<std::vector<int>> yss(n);

    yss[0].push_back(s);
    yss[n - 1].push_back(t);
    while (m--) {
        int x, y1, y2;
        std::cin >> x >> y1 >> y2;
        --x, --y1, --y2;

        yss[x].push_back(y1);
        yss[x + 1].push_back(y2);
        es.emplace_back(enc(x, y1), enc(x + 1, y2));
    }

    std::vector<lint> vs;
    for (int x = 0; x < n; ++x) {
        auto& ys = yss[x];
        compress(ys);
        for (auto y : ys) vs.push_back(enc(x, y));
    }

    auto vrev = compress(vs);
    int nn = vs.size();

    Graph<lint> graph(nn);
    for (auto [u, v] : es) graph.span(true, vrev[u], vrev[v], 0);

    for (int x = 0; x < n; ++x) {
        auto& ys = yss[x];
        int l = ys.size();

        for (int i = 0; i + 1 < l; ++i) {
            int u = vrev[enc(x, ys[i])],
                v = vrev[enc(x, ys[i + 1])];
            graph.span(false, u, v, ys[i + 1] - ys[i]);
        }
    }

    auto ds = dijkstra(graph, vrev[enc(0, s)]);
    auto ans = ds[vrev[enc(n - 1, t)]];
    std::cout << ans << "\n";
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}
0