fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<cstdio>
  3. #include<cctype> 
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8. typedef double db;
  9. typedef vector <int>  vi;
  10. typedef queue <int> qi;
  11. typedef queue < char > qc;
  12. typedef queue < string > qs;
  13. typedef vector < char > vc;
  14. typedef vector < string > vs;
  15. typedef pair < int, int >  pii;
  16. typedef pair < long long, long long >  pll;
  17. typedef vector < pair < int, int > >  vpii;
  18. typedef vector < pair < long long, long long > >  vpll;
  19. #define mp make_pair
  20. #define pb push_back
  21. #define ff first
  22. #define ss second
  23. #define mod 1000000007
  24. #define INF 0x3f3f3f3f 
  25. #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
  26.  
  27.  
  28. void checkNupdate(vector<pair<int,pii>> &open,int tc, int pc, int v){
  29.     for(auto it = open.begin(); it != open.end(); ++it){
  30.         if((*it).ss.ss == v){
  31.             (*it).ss.ff = pc;
  32.             (*it).ff = tc;
  33.             return;
  34.         }
  35.     }
  36. }
  37. // distance to the nearest unvisited city from the current city
  38. int h1(int *adj[], int v, vector<int> leftItems){
  39.     int x = leftItems.size() > 1 ? INT_MAX : 0;
  40.     for(auto it = leftItems.begin(); it != leftItems.end(); ++it){
  41.         if(adj[v][*it] < x && *it != v){
  42.             x = adj[v][*it];
  43.         }
  44.     }
  45.     return x;
  46. }
  47. // nearest distance from an unvisited city to the start city
  48. int h2(int *adj[], int v, vector<int> leftItems){
  49.     int x = leftItems.size() > 1 ? INT_MAX : 0;
  50.     for(auto it = leftItems.begin(); it != leftItems.end(); ++it){
  51.         if(adj[0][*it] < x && *it != v){
  52.             x = adj[0][*it];
  53.         }
  54.     }
  55.     return x;
  56. }
  57.  
  58. int calcPathCost(vector<pair<int,int>> adj[], int u,int v){
  59.     for(auto it = adj[u].begin(); it != adj[u].end(); ++it){
  60.         if((*it).ff == v) return (*it).ss;
  61.     }
  62. }
  63.  
  64. int checkOpen(vector<pair<int,pii>> open,int v){
  65.     for(auto it = open.begin(); it != open.end(); ++it){
  66.         if((*it).ss.ss == v) return (*it).ff;
  67.     }
  68. }
  69.  
  70. // This structure represents a directed graph using
  71. // adjacency list representation
  72. struct Graph { 
  73. 	int V; //No. of vertices 
  74.     /* Print MST using Prim's algorithm */
  75.     int primMST();
  76.     // In a weighted graph, we need to store vertex 
  77.     // and weight pair for every edge
  78.     list<pii> *edges; 
  79. 	Graph(int V) { 
  80.         this->V = V; 
  81.         edges = new list<pii> [V]; 
  82.     } 
  83. 	/* function to add an edge to graph */
  84. 	void addEdge(int u, int v, int w){ 
  85.         edges[u].pb(mp(v, w)); 
  86.         edges[v].pb(mp(u, w)); 
  87.     }  	 
  88. }; 
  89.  
  90. /* Prints shortest paths from src to all other vertices */
  91. int Graph::primMST() 
  92. { 
  93. 	/* Create a priority queue to store vertices that 
  94. 	 are being preinMST. This is weird syntax in C++.*/ 
  95.  
  96.     // Reference : http://g...content-available-to-author-only...z.com/implement-min-heap-using-stl/
  97. 	priority_queue< pii, vector <pii> , greater<pii> > pq; 
  98.  
  99. 	int src = 0; // Taking vertex 0 as source
  100.  
  101. 	/* 
  102.     Create a vector for keys and initialize all 
  103. 	keys as infinite (INF)
  104.     */
  105. 	vector<int> key(V, INF); 
  106.  
  107. 	/* To store parent array which in turn store MST*/ 
  108. 	vector<int> parent(V, -1); 
  109.  
  110. 	/* To keep track of vertices included in MST */
  111. 	vector<bool> inMST(V, false); 
  112.  
  113. 	/* Insert source itself in priority queue and initialize 
  114. 	 its key as 0. */
  115. 	pq.push(mp(0, src)); 
  116. 	key[src] = 0; 
  117.  
  118. 	/* Looping till priority queue becomes empty */
  119. 	while (!pq.empty()) 
  120. 	{ 
  121. 		/* The ff vertex in pair is the minimum key 
  122. 		vertex, extract it from priority queue. 
  123. 		vertex label is stored in ss of pair (it 
  124. 		has to be done this way to keep the vertices 
  125. 		sorted key (key must be ff item 
  126. 		in pair) */
  127. 		int u = pq.top().ss; 
  128. 		pq.pop(); 
  129.  
  130. 		inMST[u] = true; // Include vertex in MST
  131.  
  132. 		/*'i' is used to get all adjacent vertices of a vertex */
  133. 		list< pair<int, int> >::iterator i; 
  134. 		for (i = edges[u].begin(); i != edges[u].end(); ++i) 
  135. 		{ 
  136. 			/* Get vertex label and weight of current adjacent 
  137. 			 of u. */
  138. 			int v = (*i).ff; 
  139. 			int weight = (*i).ss; 
  140.  
  141. 			/* If v is not in MST and weight of (u,v) is smaller 
  142. 			than current key of v */
  143. 			if (inMST[v] == false && key[v] > weight) 
  144. 			{ 
  145. 				/*Updating key of v */
  146. 				key[v] = weight; 
  147. 				pq.push(mp(key[v], v)); 
  148. 				parent[v] = u; 
  149. 			} 
  150. 		} 
  151.  
  152. 	} 
  153. 	int total_weigh = 0;
  154. 	//Calculate Weight of MST
  155. 	for (int i = 1; i < V; ++i) {
  156.         for(auto k : edges[i]){
  157.        	    if(k.ff == parent[i])
  158.                 total_weigh+=k.ss;
  159.         }
  160.     }
  161.  
  162.     return total_weigh;
  163. } 
  164.  
  165. int h_x(int v, int *adj[], vector<int> leftItems){
  166.     int x, y, z;
  167.     // distance to the nearest unvisited city from the current city
  168.     x = h1(adj,v,leftItems);
  169.     // nearest distance from an unvisited city to the start city
  170.     y = h2(adj,v,leftItems);
  171.  
  172.     // estimated distance to travel all the unvisited cities
  173.     // (MST heuristic used here)
  174.     // Create a graph and add all edges below current node
  175.     Graph graph(leftItems.size()-1);
  176.     int i = 0, j = 0;
  177.     for(auto it = leftItems.begin(); it != leftItems.end(); ++it){
  178.         if(*it != v){ j = i+1;
  179.             for(auto jt = it+1; jt != leftItems.end(); ++jt){
  180.                 if(*jt != v){
  181.                     graph.addEdge(i,j,adj[*it][*jt]);
  182.                     ++j;
  183.                 }
  184.             }
  185.             ++i;
  186.         }
  187.     }
  188.     // calculate mst_weight
  189.     z = graph.primMST();
  190.     return x+y+z;
  191. }
  192.  
  193. int a_Star(int **adj, int V){
  194.     //open list of vertices
  195.     vector<pair<int,pii>> open;
  196.     //close list of verices
  197.     vector<int> close;
  198.     //left vertices
  199.     vector<int> leftItems;
  200.     for(int i = 0; i < V; ++i){
  201.         leftItems.pb(i);
  202.     }
  203.     //heuristic for first node
  204.     int heur_Cost = h_x(0,adj,leftItems);
  205.     int path_Cost = 0;
  206.     int total_Cost = heur_Cost + path_Cost;
  207.     int optimal_Cost = 0;
  208.  
  209.     open.pb( {total_Cost,{path_Cost,0}} );
  210.  
  211.     // while(!leftItems.empty()){
  212.         // finding min cost pair in open to expand
  213.         auto minI = std::min_element(open.cbegin(), open.cend(), [](const auto& lhs, const auto& rhs){
  214.             return lhs.ff < rhs.ff; 
  215.         });
  216.         //storing the extracted pair
  217.         pair<int,pii> storePair = *minI;
  218.         //removing it from open
  219.         open.erase(minI);
  220.  
  221.         int prev_path_Cost = storePair.ss.ff;
  222.  
  223.         int city = storePair.ss.ss;
  224.         close.pb(city);
  225.         //removinf from left items
  226.         leftItems.erase(find(leftItems.begin(),leftItems.end(),city));
  227.         if(leftItems.empty()){
  228.             optimal_Cost = prev_path_Cost + adj[0][city];
  229.         }
  230.  
  231.     //     for(auto it = leftItems.begin(); it != leftItems.end(); ++it){
  232.     //         heur_Cost = h_x((*it),adj,leftItems);
  233.     //         path_Cost = prev_path_Cost + adj[city][*it];
  234.     //         total_Cost = path_Cost + heur_Cost;
  235.     //         int isTCinOpen = checkOpen(open,(*it));
  236.  
  237.     //         if(isTCinOpen != -1){
  238.     //             checkNupdate(open,total_Cost,path_Cost,(*it));
  239.     //         }
  240.     //         else{
  241.     //             open.pb({total_Cost,{path_Cost,(*it)}});
  242.     //         }
  243.     //     }
  244.  
  245.     // }
  246.     return optimal_Cost;
  247. }
  248. /* Driver program to test methods of graph class */
  249. int main() 
  250. { 
  251.     // taking no of vertices
  252.     // and cost of path between each vertex
  253.  
  254. 	int V,**adj;
  255.     cout << "no. of Vertex : ";
  256.     cin >> V;
  257.     adj = new int *[V];
  258.     for(int i = 0; i < V; i++)
  259.         adj[i] = new int[V];
  260.     cout << "Cost in adjacency matrix format : " << endl;
  261.     for(int i = 0; i < V; ++i){
  262.         for(int j = 0; j < V; ++j)
  263.             cin >> adj[i][j];
  264.     }
  265.     int optimal_Cost = a_Star(adj,V);
  266.     cout << "Optimal Cost : " << optimal_Cost <<'\n';
  267. 	return 0; 
  268. } 
  269.  
Success #stdin #stdout 0s 4180KB
comments (?)
stdin
copy 
4
0 1 5 6
1 0 8 2
5 8 0 7
6 2 7 0
stdout
copy 
no. of Vertex : Cost in adjacency matrix format : 
Optimal Cost : 0
https://ideone.com/vLONAp
language:
C++14 (gcc 8.3)
created:
4 years 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!