fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  5. #define Bit(mask , i) ((mask >> i) & 1)
  6. #define fi first
  7. #define se second
  8.  
  9. const int INF = 1e9;
  10. const int N = 105;
  11.  
  12. int n , m , p;
  13. vector<pair<int , int>> adj[N];
  14.  
  15. int imp_node[12];
  16. int raw_channel[12];
  17. int imp_channel[12];
  18.  
  19. map<int , int> mp;
  20.  
  21. void inp(){
  22.     cin >> n >> m >> p;
  23.     for (int i = 1 ; i <= m ; ++i){
  24.         int u , v , w;
  25.         cin >> u >> v >> w;
  26.         adj[u].push_back({v , w});
  27.         adj[v].push_back({u , w});
  28.     }
  29.  
  30.     for (int i = 0 ; i < p ; ++i){
  31.         cin >> raw_channel[i] >> imp_node[i];
  32.     }
  33. }
  34.  
  35. void solve(){
  36.     int k = 0;
  37.     for (int i = 0 ; i < p ; ++i){
  38.         if (!mp.count(raw_channel[i])) mp[raw_channel[i]] = k++;
  39.     }
  40.  
  41.     for (int i = 0 ; i < p ; ++i){
  42.         imp_channel[i] = mp[raw_channel[i]];
  43.     }
  44.  
  45.     vector<int> channel_mask(1 << k , 0);
  46.  
  47.     for (int i = 0 ; i < p ; ++i){
  48.         channel_mask[imp_channel[i]] |= (1 << i);
  49.     }
  50.  
  51.     int total_mask = 1 << p;
  52.  
  53.     vector<vector<int>> dp(total_mask , vector<int>(n + 1 , INF));
  54.  
  55.     for (int i = 0 ; i < p ; ++i){
  56.         dp[1 << i][imp_node[i]] = 0;
  57.     }
  58.  
  59.     for (int mask = 1 ; mask < total_mask ; ++mask){
  60.  
  61.         for (int sub = (mask - 1) & mask ; sub ; sub = (sub - 1) & mask){
  62.             int other = mask ^ sub;
  63.             for (int i = 1 ; i <= n ; ++i){
  64.                 if (dp[sub][i] == INF || dp[other][i] == INF) continue;
  65.                 dp[mask][i] = min(dp[mask][i] , dp[sub][i] + dp[other][i]);
  66.             }
  67.         }
  68.  
  69.         priority_queue<pair<int , int> , vector<pair<int , int>> , greater<pair<int , int>>> pq;
  70.  
  71.         for (int i = 1 ; i <= n ; ++i){
  72.             if (dp[mask][i] != INF){
  73.                 pq.push({dp[mask][i] , i});
  74.             }
  75.         }
  76.  
  77.         while (!pq.empty()){
  78.             auto x = pq.top();
  79.             pq.pop();
  80.  
  81.             int du = x.fi;
  82.             int u = x.se;
  83.  
  84.             if (du != dp[mask][u]) continue;
  85.  
  86.             for (auto it : adj[u]){
  87.                 int v = it.fi;
  88.                 int w = it.se;
  89.  
  90.                 if (dp[mask][v] > du + w){
  91.                     dp[mask][v] = du + w;
  92.                     pq.push({dp[mask][v] , v});
  93.                 }
  94.             }
  95.         }
  96.     }
  97.  
  98.     vector<int> imp_mask(1 << k , 0);
  99.  
  100.     for (int mask = 1 ; mask < (1 << k) ; ++mask){
  101.         int low = mask & (-mask);
  102.         int id = __builtin_ctz(low);
  103.         imp_mask[mask] = imp_mask[mask ^ low] | channel_mask[id];
  104.     }
  105.  
  106.     vector<int> f(1 << k , INF);
  107.  
  108.     for (int mask = 1 ; mask < (1 << k) ; ++mask){
  109.         int cur = imp_mask[mask];
  110.         for (int i = 1 ; i <= n ; ++i){
  111.             f[mask] = min(f[mask] , dp[cur][i]);
  112.         }
  113.     }
  114.  
  115.     vector<int> g(1 << k , INF);
  116.     g[0] = 0;
  117.  
  118.     for (int mask = 1 ; mask < (1 << k) ; ++mask){
  119.         for (int sub = mask ; sub ; sub = (sub - 1) & mask){
  120.             int other = mask ^ sub;
  121.             if (g[other] == INF || f[sub] == INF) continue;
  122.             g[mask] = min(g[mask] , g[other] + f[sub]);
  123.         }
  124.     }
  125.  
  126.     cout << g[(1 << k) - 1];
  127. }
  128.  
  129. int main(){
  130.     faster;
  131.     inp();
  132.     solve();
  133.     return 0;
  134. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nF1gSQ
language:
C++14 (gcc 8.3)
created:
3 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!