結果
問題 | No.1601 With Animals into Institute |
ユーザー |
|
提出日時 | 2021-07-10 14:12:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 311 ms / 3,000 ms |
コード長 | 1,261 bytes |
コンパイル時間 | 3,458 ms |
コンパイル使用メモリ | 228,368 KB |
最終ジャッジ日時 | 2025-01-23 00:06:26 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef unsigned long long ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin >> n >> m; vector<vector<pair<int,pair<ll,int>>>> g(n); for(int i=0;i<m;i++){ int a,b,c,x; cin >> a >> b >> c >> x; a--; b--; g[a].push_back({b,{c,x}}); g[b].push_back({a,{c,x}}); } vector<vector<ll>> dp(2,vector<ll>(n,1e18)); priority_queue<pair<ll,pair<int,int>>,vector<pair<ll,pair<int,int>>>,greater<pair<ll,pair<int,int>>>> pq; pq.push({0,{0,n-1}}); dp[0][n-1]=0; while(pq.size()){ auto p=pq.top(); pq.pop(); int f=p.second.first,s=p.second.second; if(p.first!=dp[f][s])continue; for(auto to:g[s]){ int nxf=f|(to.second.second); ll cost=p.first+to.second.first; int t=to.first; if(dp[nxf][t]>cost){ dp[nxf][t]=cost; pq.push({cost,{nxf,t}}); } } } for(int i=0;i+1<n;i++){ printf("%lld\n",dp[1][i]); } }