結果
問題 | No.3111 Toll Optimization |
ユーザー |
|
提出日時 | 2025-04-18 21:23:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 102 ms / 5,000 ms |
コード長 | 5,868 bytes |
コンパイル時間 | 3,327 ms |
コンパイル使用メモリ | 243,844 KB |
実行使用メモリ | 17,328 KB |
最終ジャッジ日時 | 2025-04-18 21:23:31 |
合計ジャッジ時間 | 8,409 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ar array #define int long long #define ll long long #define ld long double #define pb push_back #define eb emplace_back #define pob pop_back() #define nn "\n" #define onn << "\n" #define ee endl #define oee << endl #define ss " " #define oss << " " #define sei unordered_set<int, custom_hash> #define ses unordered_set<string> #define ma unordered_map #define maii unordered_map<int, int, custom_hash> #define vc vector #define id1 int n; cin >> n; #define gls getline(cin, s) #define sinf 1e9 #define inf (int) 1e18 #define co cout << #define sp(i) setprecision(i) << #define f1(i, a) for (auto& i : a) #define f2(i, j, a) for (auto& [i, j] : a) #define f3(i, j, k, a) for (auto& [i, j, k] : a) #define be(s) s.begin(), s.end() #define rbe(s) s.rbegin(), s.rend() #define bb(s) s.begin(), s.begin() #define ctz(x) __builtin_ctzll(x) #define cb(x) __builtin_popcountll(x) #define ff(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define i128 __int128_t #define lb lower_bound #define ub upper_bound #define ook order_of_key #define fbo find_by_order #define fn function #define bs bitset #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef unsigned long long ull; typedef pair<int, string> pis; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<string> vs; typedef vector<double> vd; typedef vector<pair<int,int>> vp; typedef vector<vector<int>> vvi; #pragma GCC optimize("Ofast,unroll-loops") #ifdef LOCAL #include "debug_util.h" #else #define help(...) #define helpArray(...) #define io #define _time #define _siu #endif template<class T> using pq = priority_queue<T>; template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>; 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 != v.size() ? " " : "");} return os;} template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is;} struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template<class T> bool constexpr chmin(T &a, T b) { if (a > b) {a = b;return true;} return false; } template<class T> bool constexpr chmax(T &a, T b) { if (a < b) {a = b;return true;} return false; } // stable sort template <typename T> vector<int> argsort(const vector<T> &A) { vector<int> ans(sz(A)); iota(be(ans), 0); sort(be(ans), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); }); return ans; } //64b long long lsb(long long x) { return x & -x;} long long msb(long long x) { return (1ll << (63-__builtin_clzll(x))) & x;} void onb(long long& x, int i) { x |= (1ll << i);} void offb(long long& x, int i) { x &= ~(1ll << i);} bool hb(long long x, int i) { return ((1ll << i) & x) != 0;} long long bit(long long x) { return 1ll << x;} void YES(bool t = 1) { cout << (t ? "YES" : "NO") << "\n"; } void NO(bool t = 1) { YES(!t); } void Yes(bool t = 1) { cout << (t ? "Yes" : "No") << "\n"; } void No(bool t = 1) { Yes(!t); } template<typename T> vector<pair<T, int>> pfy(vector<T>& f) { vector<pair<T, int>> v; for (int i = 0; i < f.size(); i++) { v.push_back({f[i], i}); } return v; } bool inrange(int i, int j, int limi, int limj) { return i >= 0 && i < limi && j >= 0 && j < limj; } typedef tuple<int,int,int> iii; vector<char> cao = {'C','D','H','S'}; int dr8[] = {0,-1,0, 1, 1, 1, -1, -1}; int dc8[] = {-1, 0, 1, 0, 1, -1, 1, -1}; //n,w,e,s int dr[] = {-1, 0, 0, 1}; int dc[] = {0,-1,1, 0}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { uniform_int_distribution<int> uid(l, r); return uid(rng); } // Define a tree-based set with integer keys template <typename T> using Tee = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void sui() { int n,m,k; cin>>n>>m>>k; vi cost(m); cin>>cost; vc<vp> al(n); ff(i,0,m) { int x,y; cin>>x>>y; --x,--y; al[x].eb(y, cost[i]); al[y].eb(x, cost[i]); } vvi d(k+1, vi(n + 1, inf)); vc<vb> vis(k+1, vb(n + 1, 0)); pqg<iii> q; q.push({0, k, 0}); d[k][0] = 0; while(!q.empty()) { auto [a,b,c] = q.top(); if (c == n-1) { co a onn; return; } q.pop(); if(vis[b][c]) continue; vis[b][c] = 1; for(auto [i,j]: al[c]) { if(d[b][c] + j < d[b][i]) { d[b][i] = d[b][c] + j; q.push({d[b][i], b, i}); } if (b > 0) { if(d[b][c] < d[b-1][i]) { d[b-1][i] = d[b][c]; q.push({d[b-1][i], b-1, i}); } } } } co -1 onn; } signed main() { cin.tie(NULL); ios_base::sync_with_stdio(false); auto start = std::chrono::high_resolution_clock::now(); io; int n = 1; // cin >> n; ff(i,0,n) sui(); _time; return 0; }