結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:31:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 2,503 bytes |
コンパイル時間 | 6,523 ms |
コンパイル使用メモリ | 333,204 KB |
実行使用メモリ | 19,304 KB |
最終ジャッジ日時 | 2025-09-06 13:32:07 |
合計ジャッジ時間 | 9,069 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’: main.cpp:62:25: warning: narrowing conversion of ‘n’ from ‘ll’ {aka ‘long long int’} to ‘size_t’ {aka ‘long unsigned int’} [-Wnarrowing] 62 | auto memo = make_v({n,5},LINF); | ^
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i,j,n) for(ll i=j;i<(ll)(n);i++) #define rrep(i,j,n) for(ll i=j;i>=n;i--) #define all(x) (x).begin(),(x).end() #define m0(x) memset(x,0,sizeof(x)) #define pb emplace_back #define mp make_pair #define perm(c) sort(all(c)); for(bool c##p=1;c##p;c##p=next_permutation(all(c))) #define UNIQUE(v) sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()) using namespace std; using namespace atcoder; typedef long long ll; typedef unsigned long long ull; typedef long double ld; template<class T> bool chmax(T &a, const T &b){if(a<b) {a=b;return 1;}return 0;} template<class T> bool chmin(T &a, const T &b){if(a>b) {a=b;return 1;}return 0;} const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 1; namespace detail { template <typename Tp, size_t Nb> auto make_v(std::vector<size_t>& sizes, Tp const& x) { if constexpr (Nb == 1) { return std::vector(sizes[0], x); } else { size_t size = sizes[Nb-1]; sizes.pop_back(); return std::vector(size, make_v<Tp, Nb-1>(sizes, x)); } } } // detail:: template <typename Tp, size_t Nb> auto make_v(size_t const(&sizes)[Nb], Tp const& x = Tp()) { std::vector<size_t> s(Nb); for (size_t i = 0; i < Nb; ++i) s[i] = sizes[Nb-i-1]; return detail::make_v<Tp, Nb>(s, x); } ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} void yn(bool ok){ if(ok) cout << "Yes\n"; else cout << "No\n"; } void solve(){ ll n,m; cin >> n >> m; vector<vector<ll>> graph(n); rep(i,0,m){ ll u,v; cin >> u >> v; u--;v--; graph[u].pb(v); graph[v].pb(u); } ll k; cin >> k; vector<ll> stone(n,0); rep(i,0,k){ ll v; cin >> v; stone[v-1] = 1; } auto memo = make_v({n,5},LINF); queue<tuple<ll,ll,ll>> que; que.push({0,0,0}); while(!que.empty()){ auto [d,v,s] = que.front(); que.pop(); if(d >= memo[v][s]) continue; memo[v][s] = d; for(auto u : graph[v]){ if(stone[u]){ if(s < 4) que.push({d+1,u,s+1}); } else{ que.push({d+1,u,0}); } } } ll ans = LINF; rep(i,0,4) chmin(ans,memo[n-1][i]); if(ans == LINF) cout << "-1\n"; else cout << ans << "\n"; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); ll T; T = 1; /* cin >> T; */ while(T--) solve(); }