結果
問題 | No.468 役に立つ競技プログラミング実践編 |
ユーザー |
|
提出日時 | 2017-05-05 05:11:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 360 ms / 2,000 ms |
コード長 | 1,790 bytes |
コンパイル時間 | 967 ms |
コンパイル使用メモリ | 76,544 KB |
実行使用メモリ | 23,488 KB |
最終ジャッジ日時 | 2024-09-14 08:03:31 |
合計ジャッジ時間 | 6,229 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 31 |
other | AC * 6 |
ソースコード
#include <iostream> #include <vector> #include <limits> int n, m; std::vector<std::vector<int> > edge1; std::vector<std::vector<int> > edge2; std::vector<int> ent, lnt; std::vector<int> rec, ser; void calc_ent(int node) { if (rec[node] != 0) { return; } for (int i = 0; i < edge1[node].size() / 2; i++) { int id = 2 * i; int t = ent[node] + edge1[node][id + 1]; if (t > ent[edge1[node][id]]) { ent[edge1[node][id]] = t; } rec[edge1[node][id]]--; calc_ent(edge1[node][id]); } rec[node]--; return; } void calc_lnt(int node) { if (ser[node] != 0) { return; } for (int i = 0; i < edge2[node].size() / 2; i++) { int id = 2 * i; int t = lnt[node] - edge2[node][id + 1]; if (t < lnt[edge2[node][id]]) { lnt[edge2[node][id]] = t; } ser[edge2[node][id]]--; calc_lnt(edge2[node][id]); } ser[node]--; return; } int main() { int tmp[3] = {0}; int c = 0; std::cin >> n >> m; edge1.resize(n); edge2.resize(n); ent.resize(n, 0); ent[0] = 0; lnt.resize(n, std::numeric_limits<int>::max()); rec.resize(n, 0); ser.resize(n, 0); for (int i = 0; i < m; i++) { std::cin >> tmp[0] >> tmp[1] >> tmp[2]; edge1[tmp[0]].push_back(tmp[1]); edge1[tmp[0]].push_back(tmp[2]); edge2[tmp[1]].push_back(tmp[0]); edge2[tmp[1]].push_back(tmp[2]); ser[tmp[0]]++; rec[tmp[1]]++; } calc_ent(0); lnt[n-1] = ent[n-1]; calc_lnt(n-1); for (int i = 0; i < n; i++) { if (lnt[i] != ent[i]) { c++; } } std::cout << ent[n-1] << " " << c << "/" << n << std::endl; }