結果

問題 No.468 役に立つ競技プログラミング実践編
ユーザー kanetai
提出日時 2025-06-20 23:29:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 384 ms / 2,000 ms
コード長 2,287 bytes
コンパイル時間 1,046 ms
コンパイル使用メモリ 89,476 KB
実行使用メモリ 25,192 KB
最終ジャッジ日時 2025-06-20 23:29:44
合計ジャッジ時間 6,311 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 31
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct Edge {
    int from;
    int to;
    ll cost;
};

using Graph = vector<vector<Edge> >;

// トポロジカルソート
vector<int> topological_sort(const Graph& G) {
    int N = G.size();
    vector<int> indegree(N, 0);
    for (int u = 0; u < N; ++u) {
        for (const auto& e : G[u]) {
            indegree[e.to]++;
        }
    }

    queue<int> q;
    for (int i = 0; i < N; ++i) {
        if (indegree[i] == 0) q.push(i);
    }

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (const auto& e : G[u]) {
            if (--indegree[e.to] == 0) {
                q.push(e.to);
            }
        }
    }

    if ((int)order.size() != N) {
        throw runtime_error("Graph is not a DAG.");
    }

    return order;
}

// 最早開始時刻（EST）
vector<ll> calc_EST(const vector<int>& order, const Graph& G) {
    int N = G.size();
    vector<ll> EST(N, 0);
    for (int u : order) {
        for (const auto& e : G[u]) {
            EST[e.to] = max(EST[e.to], EST[u] + e.cost);
        }
    }
    return EST;
}

// 最遅開始時刻（LST）
vector<ll> calc_LST(const vector<int>& revOrder, const Graph& revG, ll T) {
    int N = revG.size();
    const ll INF = 1LL << 60;
    vector<ll> LST(N, INF);
    LST[revOrder[0]] = T;
    for (int v : revOrder) {
        for (const auto& e : revG[v]) {
            LST[e.from] = min(LST[e.from], LST[v] - e.cost);
        }
    }
    return LST;
}

int main() {
    int N, M;
    cin >> N >> M;

    Graph G(N), revG(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        ll c;
        cin >> u >> v >> c;
        Edge e = {u, v, c};
        G[u].push_back(e);
        revG[v].push_back(e);
    }

    vector<int> topo = topological_sort(G);
    vector<int> revTopo = topo;
    reverse(revTopo.begin(), revTopo.end());

    vector<ll> EST = calc_EST(topo, G);
    ll T = EST[revTopo[0]];
    vector<ll> LST = calc_LST(revTopo, revG, T);

    int slackCount = 0;
    for (int i = 0; i < N; ++i) {
        if (LST[i] > EST[i]) slackCount++;
    }

    cout << T << " " << slackCount << "/" << N << endl;
    return 0;
}
0