結果
問題 | No.468 役に立つ競技プログラミング実践編 |
ユーザー |
|
提出日時 | 2016-12-18 00:12:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 853 bytes |
コンパイル時間 | 1,806 ms |
コンパイル使用メモリ | 171,152 KB |
実行使用メモリ | 15,616 KB |
最終ジャッジ日時 | 2024-12-14 04:41:25 |
合計ジャッジ時間 | 4,390 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 31 |
other | AC * 6 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct Edge { int v; int w; }; vector<Edge> g[100000]; int cost[100000]; bool vis[100000]; void dfs(int u) { if (cost[u] != 0) { return; } for (Edge e : g[u]) { dfs(e.v); cost[u] = max(cost[u], cost[e.v] + e.w); } } void dfs2(int u) { if (vis[u]) { return; } vis[u] = true; for (Edge e : g[u]) { if (cost[u] == cost[e.v] + e.w) { dfs2(e.v); } } } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); g[a].push_back({ b, c }); } dfs(0); dfs2(0); int cnt = 0; for (int i = 0; i < n; i++) { cnt += vis[i]; } cout << cost[0] << " " << (n - cnt) << "/" << n << endl; }