//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
#include<bits/stdc++.h>
#define all(x) (x).begin() , (x).end()
#define pll pair<int , int>
#define fi first
#define se second
#define bit(i,j) ((j >> i) & 1)
using namespace std;
const long long inf = 1e9+1;
const int mod = 998244353;
const int MAXN = 1e5+100;
#define int long long
int dp[64][MAXN];
vector<pll> adj[MAXN];
int32_t main(){
//freopen("PAINT.INP", "r", stdin);
//freopen("PAINT.OUT", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n , k , m; cin >> n >> k >> m;
vector<int> a(k+1);
for(int i = 0 ; i < (1 << k) ; i++){
for(int j = 1 ; j <= n ; j++) dp[i][j] = inf;
}
for(int i = 1 ; i <= k ; i++) cin >> a[i] , dp[(1 << (i-1))][a[i]] = 0;
for(int i = 1 ; i <= m ; i++){
int x , y , w; cin >> x >> y >> w;
adj[x].push_back({y , w});
adj[y].push_back({x , w});
}
struct cmp{
bool operator() (const pll &a , const pll &b) const {
return a.se > b.se;
}
};
priority_queue<pll , vector<pll> , cmp> Q;
for(int msk = 1 ; msk < (1 << k) ; msk++){
for(int s = (msk - 1) & msk ; s >= 1 ; s = (s - 1) & msk){
for(int i = 1 ; i <= n ; i++){
dp[msk][i] = min(dp[s][i] + dp[msk ^ s][i] , dp[msk][i]);
}
}
for(int i = 1 ; i <= n ; i++){
Q.push({i , dp[msk][i]});
}
while(Q.size() > 0){
pll t = Q.top(); Q.pop();
int u = t.fi , c = t.se;
if(c > dp[msk][u]) continue;
for(auto [v , w] : adj[u]){
if(w + c < dp[msk][v]){
dp[msk][v] = c + w;
Q.push({v , dp[msk][v]});
}
}
}
}
int ans = inf;
for(int i =1 ; i <= n ; i++) ans = min(ans , dp[(1 << k) - 1][i]);
cout << ans << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2652 KB |
Output is correct |
2 |
Correct |
1 ms |
2652 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2652 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
129 ms |
21552 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
3160 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
204 ms |
27852 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
372 ms |
40380 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |