結果

問題 No.3319 Iwaijkstra
コンテスト
ユーザー nu50218
提出日時 2025-10-31 21:13:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,418 bytes
コンパイル時間 3,559 ms
コンパイル使用メモリ 289,216 KB
実行使用メモリ 814,480 KB
最終ジャッジ日時 2025-10-31 21:13:42
合計ジャッジ時間 7,795 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// https://yukicoder.me/problems/no/3319
int iwaijkstra(int n, int m, vector<int> x, vector<int> l, vector<int> r, vector<int> c) {
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> que;
    que.emplace(0, 1);
    vector<long long> dist(n, 1e18), vis(n);
    dist[0] = 0;
    int ans(0);

    while (!que.empty()) {
        auto [a, b] = que.top();
        que.pop(), ++ans;
        if (ans >= 1e7 || que.size() >= 1e7) return 1e7;

        for (int i(0); i < n; ++i)
            if (dist[i] < a) vis[i] = true;
        if (vis[b - 1]) continue;
        for (int i(0); i < m; ++i)
            if (x[i] == b) {
                for (int j(l[i] - 1); j < r[i]; ++j)
                    if (!vis[j]) {
                        dist[j] = min(dist[j], a + c[i]);
                        que.emplace(a + c[i], j + 1);
                    }
            }
    }

    return ans;
}

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

    int n, m;
    cin >> n >> m;

    vector<int> x, l, r, c;
    for (int i = 0; i < m; i++) {
        int xx, ll, rr, cc;
        cin >> xx >> ll >> rr >> cc;
        x.push_back(xx);
        l.push_back(ll);
        r.push_back(rr);
        c.push_back(cc);
    }

    int ans = iwaijkstra(n, m, x, l, r, c);

    cout << (ans == 1e7 ? "Too Many" : to_string(ans)) << endl;
}
0