結果
問題 | No.468 役に立つ競技プログラミング実践編 |
ユーザー | hirokazu1020 |
提出日時 | 2016-12-18 00:23:44 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 151 ms / 2,000 ms |
コード長 | 1,774 bytes |
コンパイル時間 | 1,167 ms |
コンパイル使用メモリ | 102,328 KB |
実行使用メモリ | 17,152 KB |
最終ジャッジ日時 | 2024-12-14 04:45:49 |
合計ジャッジ時間 | 4,045 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 31 |
other | AC * 6 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include<sstream> #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<climits> #include<cmath> #include<string> #include<vector> #include<set> #include<map> #include<queue> #include<numeric> #include<functional> #include<algorithm> #include<bitset> #include<tuple> #include<unordered_set> #include<random> using namespace std; #define INF (1<<29) #define rep(i,n) for(int i=0;i<(int)(n);i++) #define all(v) v.begin(),v.end() #define uniq(v) v.erase(unique(all(v)),v.end()) vector<int> topologicalSort(int v, const vector<int> edge[]) { vector<int> zeros; vector<int> in(v), res; for (int i = 0; i<v; i++) { for (int j = 0; j<(int)edge[i].size(); j++)in[edge[i][j]]++; } for (int i = 0; i<v; i++)if (in[i] == 0)zeros.push_back(i); while (!zeros.empty()) { int u = zeros.back(); zeros.pop_back(); res.push_back(u); for (int i = 0; i<(int)edge[u].size(); i++) { if (--in[edge[u][i]] == 0)zeros.push_back(edge[u][i]); } } return res; } int n, m; vector<int> e[100000]; vector<pair<int, int>> edge[100000]; int dp[100000]; bool critical[100000]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; rep(i,m) { int a, b, c; cin >> a >> b >> c; e[a].push_back(b); edge[a].emplace_back(b, c); } auto ord = topologicalSort(n, e); rep(i,n) { for (auto p : edge[ord[i]]) { dp[p.first] = max(dp[p.first], dp[ord[i]] + p.second); } } critical[n - 1] = true; int cnt = 0; for (int i = n - 2; i >= 0;i--){ bool f = true; for (auto p : edge[ord[i]]) { if (critical[p.first] && dp[p.first] == dp[ord[i]] + p.second)f = false; } if (f)cnt++; else critical[ord[i]] = true; } cout << dp[n - 1] << ' ' << cnt << '/' << n << endl; return 0; }