結果

問題 No.1812 Uribo Road
ユーザー erbowl
提出日時 2022-07-25 20:57:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,168 bytes
コンパイル時間 3,397 ms
コンパイル使用メモリ 237,028 KB
最終ジャッジ日時 2025-01-30 14:02:48
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 6 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

typedef long long ll;
typedef long double ld;
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ll n,m,k;
std::cin >> n>>m>>k;
map<ll,bool> r;
set<ll> ed;
vector<tuple<ll,ll,ll>> rr;
ed.insert(0);
ed.insert(n-1);
for (int i = 0; i < k; i++) {
ll tmp;
std::cin >> tmp;
tmp--;
r[tmp] = true;
}
vector<vector<tuple<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({b, c});
edges[b].push_back({a, c});
if(r[i]){
ed.insert(a);
ed.insert(b);
rr.push_back({a,b,c});
}
}
map<ll,vector<ll>> d;
for (auto st : ed) {
auto &dn = d[st];
dn.resize(n,1e18);
dn[st] = 0;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
pq.push({0, st});
while(!pq.empty()){
auto [dis, pos] = pq.top();pq.pop();
if(dn[pos]<dis)continue;
for (auto e : edges[pos]) {
auto [v, c] = e;
if(dn[v]>dis+c){
dn[v] = dis+c;
pq.push({dn[v],v});
}
}
}
}
vector<vector<vector<ll>>> dp(1<<k, vector<vector<ll>>(ed.size(), vector<ll>(ed.size(), 1e18)));
dp[0][0][0] = 0;
ll cntt = 0;
map<ll,ll> con,con2;
for (auto e : ed) {
con[e] = cntt;
con2[cntt] = e;
cntt++;
}
for (int i = 0; i < (1<<k); i++) {
for (int j = 0; j < ed.size(); j++) {
for (int l = 0; l < ed.size(); l++) {
for (int bit = 0; bit < k; bit++) {
if(i>>bit&1){
auto [a,b,c] = rr[bit];
dp[i][j][l] = min(dp[i][j][l], dp[i&~(1<<bit)][j][con[a]]+d[b][con2[l]]+c);
dp[i][j][l] = min(dp[i][j][l], dp[i&~(1<<bit)][j][con[b]]+d[a][con2[l]]+c);
}
}
}
}
}
std::cout << dp[(1<<k)-1][0][ed.size()-1]<< std::endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0