fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long getMinimumServiceTime(int connection_nodes, vector<int> connection_from, 
  5.                            vector<int> connection_to, vector<int> connection_weight, 
  6.                            vector<int> clients) {
  7.     int m = connection_from.size();
  8.     vector<vector<pair<int, int>>> adj(connection_nodes);
  9.  
  10.     for (int i = 0; i < m; i++) {
  11.         int u = connection_from[i];
  12.         int v = connection_to[i];
  13.         int w = connection_weight[i];
  14.         adj[u].push_back({v, w});
  15.         adj[v].push_back({u, w});
  16.     }
  17.  
  18.     // Add headquarters (node 0) to clients list if not already there
  19.     vector<int> nodes;
  20.     nodes.push_back(0);
  21.     for (int c : clients) {
  22.         if (c != 0) nodes.push_back(c);
  23.     }
  24.     // Remove duplicates
  25.     sort(nodes.begin(), nodes.end());
  26.     nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
  27.  
  28.     int k = nodes.size();
  29.     vector<int> index_of(connection_nodes, -1);
  30.     for (int i = 0; i < k; i++) {
  31.         index_of[nodes[i]] = i;
  32.     }
  33.  
  34.     // Dijkstra from each important node
  35.     const long INF = 1e18;
  36.     vector<vector<long>> dist(k, vector<long>(connection_nodes, INF));
  37.  
  38.     for (int i = 0; i < k; i++) {
  39.         int start = nodes[i];
  40.         dist[i][start] = 0;
  41.         priority_queue<pair<long, int>, vector<pair<long, int>>, greater<pair<long, int>>> pq;
  42.         pq.push({0, start});
  43.  
  44.         while (!pq.empty()) {
  45.             auto [d, u] = pq.top(); pq.pop();
  46.             if (d != dist[i][u]) continue;
  47.             for (auto [v, w] : adj[u]) {
  48.                 if (dist[i][v] > d + w) {
  49.                     dist[i][v] = d + w;
  50.                     pq.push({dist[i][v], v});
  51.                 }
  52.             }
  53.         }
  54.     }
  55.  
  56.     // Build distance matrix between important nodes
  57.     vector<vector<long>> dmat(k, vector<long>(k, INF));
  58.     for (int i = 0; i < k; i++) {
  59.         for (int j = 0; j < k; j++) {
  60.             dmat[i][j] = dist[i][nodes[j]];
  61.         }
  62.     }
  63.  
  64.     // Check connectivity
  65.     for (int i = 0; i < k; i++) {
  66.         for (int j = 0; j < k; j++) {
  67.             if (dmat[i][j] >= INF) return -1;
  68.         }
  69.     }
  70.  
  71.     // TSP DP
  72.     int fullmask = (1 << k) - 1;
  73.     vector<vector<long>> dp(fullmask + 1, vector<long>(k, INF));
  74.     dp[1][0] = 0; // start at node 0 (which is index 0 in nodes array)
  75.  
  76.     for (int mask = 1; mask <= fullmask; mask++) {
  77.         for (int last = 0; last < k; last++) {
  78.             if (!(mask & (1 << last))) continue;
  79.             if (dp[mask][last] >= INF) continue;
  80.  
  81.             for (int nxt = 0; nxt < k; nxt++) {
  82.                 if (mask & (1 << nxt)) continue;
  83.                 int newmask = mask | (1 << nxt);
  84.                 dp[newmask][nxt] = min(dp[newmask][nxt], dp[mask][last] + dmat[last][nxt]);
  85.             }
  86.         }
  87.     }
  88.  
  89.     long ans = INF;
  90.     for (int last = 0; last < k; last++) {
  91.         if (dp[fullmask][last] < INF) {
  92.             ans = min(ans, dp[fullmask][last] + dmat[last][0]);
  93.         }
  94.     }
  95.  
  96.     return ans;
  97. }
  98.  
  99. int main() {
  100.     int connection_nodes, m;
  101.     cin >> connection_nodes >> m;
  102.     vector<int> connection_from(m), connection_to(m), connection_weight(m);
  103.     for (int i = 0; i < m; i++) {
  104.         cin >> connection_from[i] >> connection_to[i] >> connection_weight[i];
  105.     }
  106.     int k;
  107.     cin >> k;
  108.     vector<int> clients(k);
  109.     for (int i = 0; i < k; i++) {
  110.         cin >> clients[i];
  111.     }
  112.  
  113.     long result = getMinimumServiceTime(connection_nodes, connection_from, connection_to, connection_weight, clients);
  114.     cout << result << endl;
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10
aba
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
geeksforgeeks
stdout
copy 
0
https://ideone.com/j51GMM
language:
C++ (gcc 8.3)
created:
5 hours 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!