SHARE
TWEET

TSP

a guest Dec 2nd, 2019 112 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define D(x) cout<<#x<<" = " <<x<<endl
  4. #define mx 10000
  5. #define inf 1e9
  6.  
  7. vector<int> edge[mx];
  8. int cost[mx][mx];
  9. vector<int> new_mst[mx];
  10. int arr[mx+5];
  11. int n, m, t, u, v, w, idx = 0;
  12.  
  13. int parent[mx], visited[mx], value[mx];
  14. map<int, string> mp;
  15.  
  16. void dfs(int src);
  17. void solve();
  18.  
  19. struct Node
  20. {
  21.     int x, d;
  22. }ND;
  23.  
  24. bool operator < (Node A, Node B)
  25. {
  26.     if(A.d<B.d) return false;
  27.     return true;
  28. }
  29.  
  30. void init()
  31. {
  32.     for(int i =0; i< mx; i++){
  33.         edge[i].clear();
  34.         new_mst[i].clear();
  35.     }
  36.     mp[0] = "Dhaka";
  37.     mp[1] = "Rajsahi";
  38.     mp[2] = "Khulna";
  39.     mp[4] = "Barishal";
  40.     mp[3] = "chattogram";
  41.     mp[5] = "Syhlet";
  42. }
  43.  
  44. void print()
  45. {
  46.     cout<<endl;
  47.     D("MST ");
  48.     int idx;
  49.     for(int i =0 ; i< n;i++)
  50.     {
  51.         int p = parent[i];
  52.         if(p == -1) cout<<"Root is "<<mp[i]<<endl, idx = i;
  53.         else{
  54.                 cout<<mp[p]<<" to " <<mp[i]<<" = "<<value[i]<<endl;
  55.                 //printf(" %d to %d = %d\n",mp[p], mp[i], value[i]);
  56.                 new_mst[p].push_back(i);
  57.         }
  58.     }
  59.     cout<<endl;
  60.     memset(visited, 0, sizeof visited);
  61.     dfs(idx);
  62.     cout<<" "<<mp[0]<<endl;
  63.     solve();
  64. }
  65.  
  66. void mst(int src)
  67. {
  68.     memset(visited,0, sizeof visited);
  69.     memset(parent, -1, sizeof parent);
  70.     for(int i =0; i< n;i++) value[i] = inf;
  71.  
  72.     value[src] = 0;
  73.     ND.x = src;
  74.     ND.d = value[src];
  75.     visited[src] = 1;
  76.  
  77.     priority_queue<Node> q;
  78.     q.push(ND);
  79.  
  80.     while(!q.empty())
  81.     {
  82.         Node u;
  83.         u = q.top();
  84.         q.pop();
  85.         visited[u.x] = 1;
  86.         //printf("Node %d : %d",)
  87.         for(int i = 0; i< edge[u.x].size(); i++)
  88.         {
  89.             Node v;
  90.             v.x = edge[u.x][i];
  91.             v.d = cost[u.x][v.x];
  92.             //printf("Node %d to %d : %d\n",u.x,v.x,v.d);
  93.             if(!visited[v.x] && value[v.x] > v.d)
  94.             {
  95.                 value[v.x] = v.d;
  96.                 parent[v.x] = u.x;
  97.  
  98.                 q.push(v);
  99.             }
  100.         }
  101.     }
  102.     print();
  103. }
  104.  
  105.  
  106. void dfs(int src)
  107. {
  108.     arr[idx++] = src;
  109.     cout<<mp[src]<<" -> ";
  110.    // printf("%s -> ", src);
  111.     for(int i =0; i< new_mst[src].size(); i++)
  112.     {
  113.         dfs(new_mst[src][i]);
  114.     }
  115. }
  116.  
  117. void solve()
  118. {
  119.     cout<<endl;
  120.     int ret = 0;
  121.     arr[n] = 0;
  122.     for(int i = 0; i< n;i++)
  123.     {
  124.         int q, ww;
  125.         q = arr[i];ww = arr[i+1];
  126.         cout<<mp[q]<<" -> " <<mp[ww]<<" = " <<cost[q][ww]<<endl;
  127.         //printf("Edge %d to %d = %d\n",arr[i],arr[i+1],cost[arr[i]][arr[i+1]]);
  128.         ret+=cost[arr[i]][arr[i+1]];
  129.     }
  130.     cout<<endl;
  131.     D(ret);
  132. }
  133.  
  134. int main()
  135. {
  136.     freopen("input.txt","r",stdin);
  137.     cin>>t;
  138.     while(t--)
  139.     {
  140.         init();
  141.         cin>>n>>m;
  142.         for(int i=0; i< m ;i++)
  143.         {
  144.             cin>>u>>v>>w;
  145.             edge[u].push_back(v);
  146.             edge[v].push_back(u);
  147.             cost[u][v] = w;
  148.             cost[v][u] = w;
  149.         }
  150.         mst(0);
  151.     }
  152.  
  153.     return 0;
  154. }
  155.  
  156.  
  157.  
  158. /* input
  159. 1
  160. 6 15
  161. 0 2 141
  162. 0 1 121
  163. 0 3 214
  164. 0 4 163
  165. 0 5 191
  166. 2 1 197
  167. 2 3 237
  168. 2 4 85
  169. 2 5 330
  170. 1 3 395
  171. 1 4 258
  172. 1 5 336
  173. 3 4 152
  174. 3 5 280
  175. 4 5 290
  176.  
  177. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top