fork download
copy 
  1. // Đạt đz s1 tg
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define f first
  6. #define s second
  7. #define mod 1000000007
  8. #define PB push_back
  9. #define PF push_front
  10. #define inf 10000007
  11. #define round(m,n) setprecision((int)m) << fixed << double(n)
  12. #define ll long long
  13. #define int long long
  14. #define bit(x, i) ((x >> i) & 1)
  15. #define pii pair<int, int>
  16. #define TASK "snow"
  17.  
  18. using namespace std;
  19.  
  20. void ADD(int &x, int y){
  21.     x += y;
  22.     if (x >= mod) x -= mod;
  23.     if (x < 0) x += mod;
  24. }
  25.  
  26. int n, m, k, t;
  27. vector<pii> adj[105];
  28. int a[105];
  29.  
  30. struct gay{
  31.     int u, v, w;
  32. } b[100005];
  33.  
  34. int comp(gay a, gay b){
  35.     return a.w < b.w;
  36. }
  37.  
  38. int r[105];
  39. int get(int x){
  40.     if(r[x] == x) return x;
  41.     return r[x] = get(r[x]);
  42. }
  43. void join(int x, int y){
  44.     int u = get(x), v = get(y);
  45.     if(u == v) return;
  46.     r[v] = u;
  47. }
  48. int check(int x, int y){
  49.     int u = get(x), v = get(y);
  50.     return (u == v);
  51. }
  52.  
  53. void sub1(){
  54.     sort(b + 1, b + m + 1, comp);
  55.     for(int i = 1; i <= n; i++)
  56.         r[i] = i;
  57.  
  58.     int cnt = 0;
  59.     for(int i = 1; i <= m; i++){
  60.         auto [u, v, w] = b[i];
  61.         if(!check(u, v)){
  62.             join(u, v);
  63.             cnt += w;
  64.         }
  65.     }
  66.  
  67.     cout << cnt;
  68. }
  69.  
  70. int w[105][105];
  71. void sub2(){
  72.     for(int i = 1; i <= n; i++)
  73.     for(int j = 1; j <= n; j++){
  74.         if(i == j) continue;
  75.         w[i][j] = 1e15;
  76.     }
  77.     for(int i = 1; i <= m; i++){
  78.         auto [u, v, W] = b[i];
  79.         w[u][v] = min(W, w[u][v]);
  80.         w[v][u] = w[u][v];
  81.     }
  82.     for(int t = 1; t <= n; t++)
  83.     for(int i = 1; i <= n; i++)
  84.     for(int j = 1; j <= n; j++)
  85.     w[i][j] = min(w[i][j], w[i][t] + w[t][j]);
  86.  
  87.     cout << w[a[1]][a[2]];
  88. }
  89.  
  90. void sub3(){
  91.     for(int i = 1; i <= n; i++)
  92.     for(int j = 1; j <= n; j++){
  93.         if(i == j) continue;
  94.         w[i][j] = 1e15;
  95.     }
  96.     for(int i = 1; i <= m; i++){
  97.         auto [u, v, W] = b[i];
  98.         w[u][v] = min(W, w[u][v]);
  99.         w[v][u] = w[u][v];
  100.     }
  101.     for(int t = 1; t <= n; t++)
  102.     for(int i = 1; i <= n; i++)
  103.     for(int j = 1; j <= n; j++)
  104.     w[i][j] = min(w[i][j], w[i][t] + w[t][j]);
  105.  
  106.     int minn = 1e15;
  107.     for(int i = 1; i <= k; i++)
  108.     for(int j = 1; j <= k; j++)
  109.     for(int z = 1; z <= k; z++)
  110.     if(a[i] != a[j] && a[j] != a[z] && a[i] != a[z]){
  111.         for(int x = 1; x <= n; x++)
  112.         for(int y = 1; y <= n; y++)
  113.         minn = min(minn, w[a[i]][x] + w[x][a[j]] + w[a[j]][y] + w[y][a[z]]);
  114.     }
  115.  
  116.     for(int x = 1; x <= n; x++){
  117.         for(int i = 1; i <= k; i++)
  118.         for(int j = 1; j <= k; j++)
  119.         for(int z = 1; z <= k; z++)
  120.         if(a[i] != a[j] && a[j] != a[z] && a[i] != a[z]){
  121.             minn = min(minn, w[a[i]][x] + w[a[j]][x] + w[a[z]][x]);
  122.         }
  123.     }
  124.  
  125.     cout << minn;
  126. }
  127.  
  128. int f[105], pick[105];
  129.  
  130. int TryMST(int mask){
  131.     for(int i = 1; i <= n; i++)
  132.         r[i] = i;
  133.  
  134.     int cnt = 0;
  135.     for(int i = 1; i <= m; i++){
  136.         auto [u, v, w] = b[i];
  137.         if(pick[u] && !f[u]) continue;
  138.         if(pick[v] && !f[v]) continue;
  139.         if(!check(u, v)){
  140.             join(u, v);
  141.             cnt += w;
  142.         }
  143.     }
  144.  
  145.     return cnt;
  146. }
  147.  
  148. void sub5(){
  149.     sort(b + 1, b + m + 1, comp);
  150.     int minn = 1e15;
  151.     for(int mask = 0; mask < (1 << k); mask++){
  152.         memset(f, 0, sizeof(f));
  153.         for(int i = 1; i <= k; i++)
  154.         f[a[i]] = bit(mask, i - 1);
  155.         minn = min(minn, TryMST(mask));
  156.     }
  157.     cout << minn;
  158. }
  159.  
  160. struct gayass{
  161.     int cost, u, mask;
  162. };
  163.  
  164. struct cmp{
  165.     bool operator()(const gayass &a, gayass &b){
  166.             return a.cost > b.cost;
  167.     }
  168. };
  169.  
  170. int conv[2025];
  171. int W[105][2025];
  172.  
  173. void sub4(){
  174.     for(int i = 1; i <= k; i++) conv[a[i]] = i;
  175.  
  176.     for(int i = 1; i <= n; i++)
  177.     for(int j = 0; j <= (1 << k); j++)
  178.         W[i][j] = 1e15;
  179.  
  180.     priority_queue<gayass, vector<gayass>, cmp> q;
  181.     for(int i = 1; i <= n; i++){
  182.         if(pick[i]){
  183.             q.push({0, i, (1 << conv[i] - 1)});
  184.             W[i][(1 << conv[i] - 1)] = 0;
  185.         }
  186.         else{
  187.             q.push({0, i, 0});
  188.             W[i][0] = 0;
  189.         }
  190.     }
  191.  
  192.     while(!q.empty()){
  193.         gayass u = q.top();
  194. //        cout << u.u << " " << u.cost << " " << u.mask << '\n';
  195.         q.pop();
  196.         for(pii v : adj[u.u]){
  197.             if(W[v.s][u.mask] > v.f + u.cost){
  198.                 W[v.s][u.mask] = v.f + u.cost;
  199.                 q.push({W[v.s][u.mask], v.s, u.mask});
  200.             }
  201.             if(conv[v.s]){
  202.                 if(bit(u.mask, conv[v.s] - 1)) continue;
  203.                 int newmask = u.mask + (1 << conv[v.s] - 1);
  204.                 if(W[v.s][newmask] > v.f + u.cost){
  205.                     W[v.s][newmask] = v.f + u.cost;
  206.                     q.push({W[v.s][newmask], v.s, newmask});
  207.                 }
  208.             }
  209.         }
  210.     }
  211.  
  212.     int ans = 1e15;
  213.     for(int i = 1; i <= n; i++)
  214. //        cout << i << " " << W[i][(1 << k) - 1] << '\n';
  215.     ans = min(ans, W[i][(1 << k) - 1]);
  216.  
  217.     cout << ans;
  218. }
  219.  
  220. signed main(){
  221.     ios_base::sync_with_stdio(0);
  222.     cin.tie(0); cout.tie(0);
  223.  
  224.     if(fopen(TASK".INP", "r")){
  225.         freopen(TASK".INP", "r", stdin);
  226.         freopen(TASK".OUT", "w", stdout);
  227.     }
  228.  
  229.     cin >> n >> k >> m >> t;
  230.     for(int i = 1; i <= k; i++){
  231.         cin >> a[i];
  232.         pick[a[i]]++;
  233.     }
  234.     for(int i = 1; i <= m; i++){
  235.         int u, v, w;
  236.         cin >> u >> v >> w;
  237.         adj[u].PB({w, v});
  238.         adj[v].PB({w, u});
  239.         b[i] = {u, v, w};
  240.     }
  241.  
  242.     if(t == 1 && k == n) sub1();
  243.     else if(t == 1 && k == 2) sub2();
  244.     else if(t == 1 && k == 3) sub3();
  245.     else if(t == 2) sub5();
  246.     else sub4();
  247. }
  248.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000
https://ideone.com/E0agql
language:
C++ (gcc 8.3)
created:
1 day 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!