Advertisement
Josif_tepe

Untitled

May 4th, 2022
758
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.83 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <queue>
  5.  
  6.  
  7. using namespace std;
  8. int n, m, k;
  9. vector<pair<int, int> > graph[40005];
  10. vector<int>v;
  11.  
  12. struct node{
  13. int idx;
  14. int cost;
  15. node(){
  16. }
  17. node(int _idx, int _cost){
  18. idx=_idx;
  19.     cost=_cost;
  20. }
  21. bool operator < (const node &temp) const{
  22.     return cost > temp.cost;
  23. }
  24.  
  25. };
  26. int dist[40005];
  27. vector<pair<int, int> > G[20];
  28.  
  29. long long dijsktra(int s){
  30. bool visited[n + 5];
  31.  
  32. for(int i=0; i<=n; i++){
  33.     visited[i]=false;
  34.     dist[i] = 2e9;
  35. }
  36.  
  37. priority_queue<node>pq;
  38. pq.push(node(s, 0));
  39.     dist[s] = 0;
  40. while(!pq.empty()){
  41.     node c=pq.top();
  42.     pq.pop();
  43.    
  44.     visited[c.idx]=true;
  45.     for(int i=0; i<graph[c.idx].size(); i++){
  46.         int sosed=graph[c.idx][i].first;
  47.         int pom=graph[c.idx][i].second;
  48.    
  49.     if((visited[sosed]==false)and(dist[sosed] > c.cost + pom)){
  50.         pq.push(node(sosed, pom));
  51.         dist[sosed]=c.cost+pom;
  52.     }
  53.     }
  54. }
  55.  
  56.    
  57.  
  58.  
  59.     return 0;
  60. }
  61. int dp[16][1 << 16];
  62. int travelling_salesmane(int node, int visited) {
  63.     if(__builtin_popcount(visited) == 1) {
  64.         for(int i = 0; i < G[node].size(); i++) {
  65.             if(G[node][i].first == 0) {
  66.                 return G[node][i].second;
  67.             }
  68.         }
  69.         return 0;
  70.     }
  71.     if(node == 0 and visited == 0) {
  72.         return 0;
  73.     }
  74.     if(dp[node][visited] != -1) {
  75.         return dp[node][visited];
  76.     }
  77.     int new_mask = visited;
  78.     new_mask -= (1 << node);
  79.     int result = 2e9;
  80.     for(int i = 0; i < G[node].size(); i++) {
  81.         int sosed = G[node][i].first;
  82.         int weight = G[node][i].second;
  83.         if(visited & (1 << sosed)) {
  84.             result = min(result, travelling_salesmane(sosed, new_mask) + weight);
  85.         }
  86.     }
  87.     return dp[node][visited] = result;
  88. }
  89. int main()
  90. {
  91.     cin>>n>>k>>m;
  92.     for(int i=0; i<k; i++){
  93.     int p;
  94.     cin>>p;
  95.     v.push_back(p);
  96.     }
  97.    
  98.    
  99.     for(int i=0; i<m; i++){
  100.     int a, b, c;
  101.    
  102.     cin>>a;
  103.     cin>>b >> c;
  104.    
  105.     graph[a].push_back(make_pair(b, c));
  106.     graph[b].push_back(make_pair(a, c));
  107.        
  108.     }
  109.    
  110.  
  111.     v.push_back(0);
  112.     for(int i = 0; i < v.size(); i++) {
  113.         dijsktra(v[i]);
  114.         for(int j = 0; j < v.size(); j++) {
  115.             if(v[i] != v[j]) {
  116.                 G[v[i]].push_back(make_pair(v[j], dist[v[j]]));
  117.                 G[v[j]].push_back(make_pair(v[i], dist[v[j]]));
  118.                
  119.             }
  120.     }
  121.     }
  122.    
  123.     int p = (int) v.size();
  124.  
  125.     for(int i = 0; i < v.size(); i++) {
  126.        
  127.         for(int j = 0; j < G[i].size(); j++) {
  128. //            cout << i << " " << G[i][j].first << " " << G[i][j].second << endl;
  129.         }
  130.     }
  131.     memset(dp, -1, sizeof dp);
  132.     cout << travelling_salesmane(0, (1 << p) - 1) << endl;
  133.    
  134.    
  135.    
  136.    
  137.    
  138.    
  139.     return 0;
  140. }
  141.  
Advertisement
RAW Paste Data Copied
Advertisement