結果
問題 | No.1812 Uribo Road |
ユーザー |
|
提出日時 | 2022-07-24 17:44:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,472 bytes |
コンパイル時間 | 2,483 ms |
コンパイル使用メモリ | 213,116 KB |
最終ジャッジ日時 | 2025-01-30 13:44:11 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 TLE * 7 MLE * 1 |
ソースコード
typedef long long ll;typedef long double ld;#include <bits/stdc++.h>using namespace std;#define int long longll k;ll cpos(ll e, ll bin){return (e<<k)+bin;}signed main(){ll n,m;std::cin >> n>>m>>k;vector<ll> r(k);map<ll,ll> rr;for (int i = 0; i < k; i++) {std::cin >> r[i];r[i]--;rr[r[i]]=i;}vector<vector<tuple<ll,ll,ll>>> edges(n);for (int i = 0; i < m; i++) {ll a,b,c;std::cin >> a>>b>>c;a--;b--;edges[a].push_back({i, b,c});edges[b].push_back({i, a,c});}vector<ll> d(n<<k,1e18);d[0] = 0;priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;pq.push({0,0});while(!pq.empty()){auto [dis, pos] = pq.top();pq.pop();ll bin = ((1<<k)-1)&pos;if(d[pos]<dis)continue;for (auto e : edges[pos>>k]) {auto [ind, nex, cost] = e;if(rr.find(ind)!=rr.end()){if(d[cpos(nex, bin|(1<<rr[ind]))]>dis+cost){d[cpos(nex, bin|(1<<rr[ind]))] = dis+cost;pq.push({dis+cost, cpos(nex, bin|(1<<rr[ind]))});}}else{if(d[cpos(nex, bin)] > dis+cost){d[cpos(nex, bin)] = dis+cost;pq.push({dis+cost, cpos(nex,bin)});}}}}std::cout << d[cpos(n-1, (1<<k)-1)] << std::endl;}