結果

問題 No.3319 Iwaijkstra
コンテスト
ユーザー nu50218
提出日時 2025-10-31 21:28:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,432 bytes
コンパイル時間 3,930 ms
コンパイル使用メモリ 308,696 KB
実行使用メモリ 272,124 KB
最終ジャッジ日時 2025-10-31 21:29:10
合計ジャッジ時間 14,021 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 11 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e7;

// 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();

        if (dist[b - 1] < a) continue;

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

    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 == INF ? "Too Many" : to_string(ans + 1)) << endl;
}
0