結果
問題 | No.2477 Drifting |
ユーザー | igeee |
提出日時 | 2023-09-18 09:28:05 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 690 ms / 2,000 ms |
コード長 | 1,912 bytes |
コンパイル時間 | 5,718 ms |
コンパイル使用メモリ | 277,284 KB |
実行使用メモリ | 38,932 KB |
最終ジャッジ日時 | 2023-09-18 09:28:20 |
合計ジャッジ時間 | 13,927 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 459 ms
36,988 KB |
testcase_01 | AC | 289 ms
25,804 KB |
testcase_02 | AC | 472 ms
37,144 KB |
testcase_03 | AC | 358 ms
18,452 KB |
testcase_04 | AC | 143 ms
11,460 KB |
testcase_05 | AC | 343 ms
16,404 KB |
testcase_06 | AC | 690 ms
38,716 KB |
testcase_07 | AC | 667 ms
38,932 KB |
testcase_08 | AC | 556 ms
35,612 KB |
testcase_09 | AC | 345 ms
30,696 KB |
testcase_10 | AC | 338 ms
34,344 KB |
testcase_11 | AC | 359 ms
26,636 KB |
testcase_12 | AC | 318 ms
31,764 KB |
testcase_13 | AC | 1 ms
4,384 KB |
testcase_14 | AC | 1 ms
4,380 KB |
testcase_15 | AC | 1 ms
4,376 KB |
testcase_16 | AC | 332 ms
26,528 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define repn(i,end) for(long long i = 0; i <= (long long)(end); i++) #define reps(i,start,end) for(long long i = start; i < (long long)(end); i++) #define repsn(i,start,end) for(long long i = start; i <= (long long)(end); i++) #define ll long long #define ld long double #define all(a) (a).begin(),(a).end() // << std::fixed << std::setprecision(10) const ll INF = 1LL << 60; template<class T> bool chmin(T& a, T b){ if(a > b){ a = b; return true; } return false; } template<class T> bool chmax(T& a, T b){ if(a < b){ a = b; return true; } return false; } //grid探索用 vector<ll> _tate = {0,-1,0,1,1,-1,-1,1}; vector<ll> _yoko = {1,0,-1,0,1,1,-1,-1}; ll lpow(ll x,ll n){ ll ans = 1; while(n >0){ if(n & 1)ans *= x; x *= x; n >>= 1; } return ans; } int main(){ ll n,m;cin >> n >> m; vector<set<pair<ll,ll>>> g(n);//頂点,距離 rep(i,m){ ll u,v,w;cin >> u >> v >> w; u--;v--; g[u].insert({v,w}); } ll K;cin >> K; set<tuple<ll,ll,ll>> abc; rep(z,K){ ll a,b,c;cin >> a >> b >> c; a--;b--;c--; abc.insert({a,b,c}); } vector<set<pair<ll,ll>>> in(n);//距離,頂点(from) vector<ll> dis(n,INF); dis[0] = 0; for(auto &p:g[0]){ in[p.first].insert({dis[0] + p.second,0}); } //0は別でやる reps(i,1,n){ for(auto &p:in[i]){ vector<pair<ll,ll>> used; auto [cost,from] = p; chmin(dis[i],cost); for(auto &q: g[i]){ auto [to,w] = q; if(abc.count({from,i,to}))continue; in[to].insert({cost + w,i}); used.push_back({to,w}); } for(auto &pr:used){ g[i].erase(pr); } } } if(dis[n-1] == INF){ cout << -1 << endl; }else{ cout << dis[n-1] << endl; } }