結果
問題 | No.468 役に立つ競技プログラミング実践編 |
ユーザー |
![]() |
提出日時 | 2024-07-29 14:41:40 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 363 ms / 2,000 ms |
コード長 | 5,090 bytes |
コンパイル時間 | 1,414 ms |
コンパイル使用メモリ | 121,516 KB |
実行使用メモリ | 18,944 KB |
最終ジャッジ日時 | 2024-07-29 14:41:48 |
合計ジャッジ時間 | 7,065 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 31 |
other | AC * 6 |
ソースコード
#include <algorithm>#include <iostream>#include <iomanip>#include <limits.h>#include <map>#include <math.h>#include <numeric>#include <queue>#include <set>#include <sstream>#include <string>#include <utility>#include <vector>#include <stack>#include <complex>using namespace std;#define rep(i, n) for (int i = 0; i < n; i++)#define rep1(i, n) for (int i = 1; i < n + 1; i++)#define rev(i, n) for (int i = n - 1; i >= 0; i--)#define all(A) A.begin(), A.end()#define itr(A, l, r) A.begin() + l, A.begin() + r#define debug(var) cout << #var << " = " << var << endl;typedef long long ll;template <typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << "(" << p.first << "," << p.second << ")";return os;}template <typename T1, typename T2>istream &operator>>(istream &is, pair<T1, T2> &p){is >> p.first >> p.second;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &v){for (int i = 0; i < (int)v.size(); i++){os << v[i] << (i + 1 != (int)v.size() ? " " : "");}return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &v){for (int i = 0; i < (int)v.size(); i++){os << v[i] << endl;}return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v){int n = v.size();int m = v[0].size();int p = v[0][0].size();rep(k, p){os << "k = " << k << endl;rep(i, n){rep(j, m){os << v[i][j][k];if (j < m - 1){os << " ";}else{os << endl;}}}}return os;}template <typename T>istream &operator>>(istream &is, vector<T> &v){for (T &in : v)is >> in;return is;}template <typename T, typename S>ostream &operator<<(ostream &os, map<T, S> &mp){for (auto &[key, val] : mp){os << key << ":" << val << " ";}cout << endl;return os;}template <typename T>ostream &operator<<(ostream &os, set<T> st){auto itr = st.begin();for (int i = 0; i < (int)st.size(); i++){os << *itr << (i + 1 != (int)st.size() ? " " : "");itr++;}return os;}template <typename T>ostream &operator<<(ostream &os, multiset<T> st){auto itr = st.begin();for (int i = 0; i < (int)st.size(); i++){os << *itr << (i + 1 != (int)st.size() ? " " : "");itr++;}return os;}template <typename T>ostream &operator<<(ostream &os, queue<T> q){while (q.size()){os << q.front() << " ";q.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, deque<T> q){while (q.size()){os << q.front() << " ";q.pop_front();}return os;}template <typename T>ostream &operator<<(ostream &os, stack<T> st){while (st.size()){os << st.top() << " ";st.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, priority_queue<T> pq){while (pq.size()){os << pq.top() << " ";pq.pop();}return os;}template <typename T>ostream &operator<<(ostream &os, priority_queue<T, vector<T>, greater<T>> mpq){while (mpq.size()){os << mpq.top() << " ";mpq.pop();}return os;}int main(){int n,m;cin >> n >> m;vector<vector<pair<int,int>>> to(n);vector<vector<pair<int,int>>> from(n);vector<int> node(n);vector<int> back_node(n);rep(i,m){int a,b,c;cin >> a >> b >> c;to[a].push_back({b,c});from[b].push_back({a,c});node[b]++;back_node[a]++;}// debug(node);queue<int> q;q.push(0);vector<int> dp(n,0);while(q.size()){int now_pos = q.front();q.pop();for(auto [next_pos,weight] : to[now_pos]){int next_cost = dp[now_pos] + weight;auto chmax = [](auto &a, auto b){ a = max(a, b); };chmax(dp[next_pos],next_cost);node[next_pos]--;if(node[next_pos] == 0){q.push(next_pos);}}}// debug(dp);q.push(n-1);vector<int> ep(n,dp[n-1]);while(q.size()){int now_pos = q.front();q.pop();for(auto [next_pos,weight] : from[now_pos]){int next_cost = ep[now_pos] - weight;auto chmin = [](auto &a, auto b){ a = min(a, b); };chmin(ep[next_pos],next_cost);back_node[next_pos]--;if(back_node[next_pos] == 0){q.push(next_pos);}}}// debug(ep);int ans = 0;rep(i,n){ans += dp[i]<ep[i];}cout << dp[n-1] << " " << ans << "/" << n << endl;}