fork download
copy 
  1. /**
  2.  *    author:  mamion
  3.  *    created: Sunday 2024-10-27
  4. **/
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #ifdef LOCAL
  10. #include<cpp-dump-main/cpp-dump.hpp>
  11. #define debug(...) cpp_dump(__VA_ARGS__)
  12. CPP_DUMP_SET_OPTION_GLOBAL(max_line_width, 100);
  13. CPP_DUMP_SET_OPTION_GLOBAL(log_label_func, cpp_dump::log_label::filename());
  14. CPP_DUMP_SET_OPTION_GLOBAL(enable_asterisk, true);
  15. #else
  16. #define debug(...)
  17. #endif // LOCAL
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double ld;
  22.  
  23. const ll mod = 1e9 + 7;
  24. template<class T> bool ckmin(T &a, T b) {return a < b ? 1 : a = b, 0;}
  25. template<class T> bool ckmax(T &a, T b) {return a > b ? 1 : a = b, 0;}
  26. template<class T> void add(T &a, T b, T m = mod) {a = (a + b) % m;};
  27. template<class T> void mul(T &a, T b, T m = mod) {a = a * b % m;}
  28.  
  29. const ll inf = 1e18;
  30. const int N = 1e5 + 10;
  31.  
  32. int n, m, k, bank[20];
  33. vector<pair<int, int>> adj[N];
  34.  
  35. ll d[20][N], dp[1 << 20];
  36.  
  37. void dijkstra(int i, int src) {
  38.     memset(d[i], 0x3f, sizeof d[i]); d[i][src] = 0;
  39.     priority_queue<pair<ll, int>> pq; pq.push({0, src});
  40.     while (pq.size()) {
  41.         int u = pq.top().second; ll dist = -pq.top().first; pq.pop();
  42.         if (d[i][u] != dist) continue;
  43.         for (auto p : adj[u]) {
  44.             int v = p.first, w = p.second;
  45.             if (d[i][v] > d[i][u] + w) {
  46.                 d[i][v] = d[i][u] + w;
  47.                 pq.push({-d[i][v], v});
  48.             }
  49.         }
  50.     }
  51. }
  52.  
  53. void solve() {
  54.     cin >> n >> m >> k;
  55.     for (int i = 0; i < k; i++) cin >> bank[i];
  56.     for (int i = 0; i < m; i++) {
  57.         int u, v, w; cin >> u >> v >> w;
  58.         adj[u].push_back({v, w});
  59.         adj[v].push_back({u, w});
  60.     }
  61.     for (int i = 0; i < k; i++) dijkstra(i, bank[i]);
  62.     memset(dp, 0x3f, sizeof dp);
  63.     for (int i = 0; i < k; i++) dp[1 << i] = 0;
  64.     for (int mask = 1; mask < (1 << k); mask++) {
  65.         for (int i = 0; i < k; i++) if (mask >> i & 1) {
  66.             for (int j = 0; j < k; j++) if ((mask >> j & 1) == 0) {
  67.                 ckmin(dp[mask | (1 << j)], dp[mask] + d[i][bank[j]]);
  68.             }
  69.         }
  70.     }
  71.     cout << dp[(1 << k) - 1];
  72. }
  73.  
  74. int main() {
  75.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  76.  
  77. #ifdef LOCAL
  78.     freopen("main.inp", "r", stdin);
  79.     freopen("main.out", "w", stdout);
  80. #else
  81.     #define file "name"
  82.     if (fopen(file".inp", "r")) {
  83.         freopen(file".inp", "r", stdin);
  84.         freopen(file".out", "w", stdout);
  85.     }
  86. #endif // LOCAL
  87.  
  88.     int T; T = 1; if (0) cin >> T;
  89.     for (int i = 1; i <= T; i++)
  90.     {
  91.         solve();
  92.     }
  93. }
  94.  
Success #stdin #stdout 0.01s 17496KB
comments (?)
stdin
copy 
6 6 2
1 4 
3 2 1
5 4 3
5 1 1
1 2 7
3 5 3
6 1 1
stdout
copy 
4
https://ideone.com/ScInH1
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!