結果

問題 No.614 壊れたキャンパス
ユーザー PachicobuePachicobue
提出日時 2017-12-14 01:10:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,048 ms / 2,000 ms
コード長 3,740 bytes
コンパイル時間 2,869 ms
コンパイル使用メモリ 237,540 KB
実行使用メモリ 149,256 KB
最終ジャッジ日時 2024-12-14 10:44:47
合計ジャッジ時間 13,086 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 859 ms
141,156 KB
testcase_09 AC 1,048 ms
149,256 KB
testcase_10 AC 736 ms
147,024 KB
testcase_11 AC 924 ms
141,064 KB
testcase_12 AC 922 ms
141,148 KB
testcase_13 AC 923 ms
141,452 KB
testcase_14 AC 856 ms
141,620 KB
testcase_15 AC 757 ms
143,356 KB
testcase_16 AC 775 ms
140,732 KB
testcase_17 AC 256 ms
114,200 KB
testcase_18 AC 456 ms
129,484 KB
testcase_19 AC 416 ms
128,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;
using ld = long double;

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}


constexpr ll MOD = (ll)1e9 + 7LL;
constexpr ld PI = static_cast<ld>(3.1415926535898);

template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;

struct CostGraph {
    using T = ll;
    CostGraph(const ll v) : V{v}
    {
        edge.resize(v);
        rev_edge.resize(v);
    }
    struct Edge {
        Edge(const ll from, const ll to, const T cost) : from{from}, to{to}, cost{cost} {}
        const ll from;
        const ll to;
        const T cost;
        bool operator<(const Edge& e) const
        {
            return cost != e.cost ? cost < e.cost : to < e.to;
        }
    };
    void addEdge(const ll from, const ll to, const T cost = 1)
    {
        edge[from].push_back(Edge{from, to, cost});
        rev_edge[to].push_back(Edge(to, from, cost));
    }
    vector<vector<Edge>> edge;
    vector<vector<Edge>> rev_edge;
    const ll V;
};

void Dijkstra(const CostGraph& g, const ll s, vector<CostGraph::T>& d)
{
    using T = CostGraph::T;
    assert(s < g.V);
    assert(d.size() == g.V);
    using P = pair<T, ll>;
    priority_queue<P, vector<P>, greater<P>> q;
    for (ll i = 0; i < g.V; i++) {
        d[i] = INF<T>;
    }
    d[s] = 0;
    q.push(make_pair(0, s));
    while (not q.empty()) {
        const P& p = q.top();
        const T cost = p.first;
        const ll v = p.second;
        q.pop();
        if (d[v] < cost) {
            continue;
        }
        for (const auto& e : g.edge[v]) {
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                q.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M, K, S, T;
    cin >> N >> M >> K >> S >> T;
    S--, T--;
    vector<ll> num(N);
    vector<tuple<ll, ll, ll>> bridge(M);
    vector<vector<ll>> pos(N);
    for (ll i = 0; i < M; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--, b--, c--;
        pos[a].push_back(b);
        num[a]++;
        pos[a + 1].push_back(c);
        num[a + 1]++;
        bridge[i] = make_tuple(a, b, c);
    }
    pos[0].push_back(S);
    num[0]++;
    pos[N - 1].push_back(T);
    num[N - 1]++;

    vector<map<ll, ll>> mps(N);
    for (ll i = 0; i < N; i++) {
        num[i] += (i == 0 ? 0 : num[i - 1]);
        sort(pos[i].begin(), pos[i].end());
        for (ll j = 0; j < pos[i].size(); j++) {
            mps[i][pos[i][j]] = j;
        }
    }
    CostGraph g(num[N - 1]);
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < (int)pos[i].size() - 1; j++) {
            g.addEdge(j + (i == 0 ? 0 : num[i - 1]), j + 1 + (i == 0 ? 0 : num[i - 1]), pos[i][j + 1] - pos[i][j]);
            g.addEdge(j + 1 + (i == 0 ? 0 : num[i - 1]), j + (i == 0 ? 0 : num[i - 1]), pos[i][j + 1] - pos[i][j]);
        }
    }
    for (ll i = 0; i < M; i++) {
        ll a, b, c;
        tie(a, b, c) = bridge[i];
        g.addEdge((a == 0 ? 0 : num[a - 1]) + mps[a][b], num[a] + mps[a + 1][c], 0);
    }
    const ll s = mps[0][S];
    const ll t = mps[N - 1][T] + (N == 1 ? 0 : num[N - 2]);

    vector<ll> dist(num[N - 1]);
    Dijkstra(g, s, dist);
    cout << (dist[t] == INF<ll> ? -1 : dist[t]) << endl;
    return 0;
}
0