fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<queue>
  6. #include<cstring>
  7. #include<map>
  8.  
  9.  
  10. using namespace std;
  11.  
  12.  
  13.  
  14.  
  15. class data
  16. {
  17. 	public:
  18. 		int u,e,cst;
  19. 	bool operator<(const data &p)const { return cst<p.cst;}
  20. };
  21.  
  22. vector<int>v[210];
  23. int cost[210][210];
  24. char store[210][35];
  25. int n,r;
  26. int parent[210];
  27. bool color[210];
  28. void prim(int src,int target)
  29. {
  30. //	memset(parent,0,sizeof(parent));
  31. 	memset(color,true,sizeof(color));
  32. 	priority_queue<data> q;
  33. //	cout<<src<<" "<<target<<endl;
  34. 	data temp,current;
  35. 	vector<int>vnew;
  36. 	int top=src,a;
  37. 	color[src]=false;
  38. 	vnew.push_back(src);
  39. 	while(vnew.size()!=n)
  40. 	{
  41.  
  42. 		for(int i=0;i<v[top].size();i++)
  43. 		{	a=v[top][i];
  44. 			if(color[a]==true)
  45. 			{
  46. //				cout<<"Pushed: "<<top<<" "<<v[top][i]<<endl;
  47. 				temp.u=top;
  48.  
  49. 				temp.e=a;
  50.  
  51. 				temp.cst=cost[top][a];
  52. 				q.push(temp);
  53. 			}
  54. 		}
  55. //		if(q.empty()) break;
  56.  
  57. 		current=q.top();
  58.  
  59. 		vnew.push_back(current.e);
  60.  
  61. 		parent[current.e]=current.u;
  62. 		if(current.e==target) break;
  63.  
  64. 		color[current.e]=false;
  65. //		cout<<current.u<<" >> "<< current.e<<endl;
  66. 		top=current.e;
  67. 		q.pop();
  68. 	}
  69.  
  70.  
  71. 	return;
  72.  
  73.  
  74. }
  75.  
  76.  
  77. int main()
  78. {
  79. 	map<string,int> m;
  80.  
  81.  
  82.    int src,target,pos1,pos2,len,d,temp,caseno=1;
  83.    char c[35];
  84.  
  85.  
  86.    bool flag=false;
  87.     while(scanf("%d%d",&n,&r)==2)
  88.     {
  89.         if(n==0 && r==0)
  90.             break;
  91.         len=1;
  92.         flag=false;
  93.         for(int i=0;i<r;i++)
  94.         {
  95.             scanf("%s",c);
  96.             if(m[c]) pos1=m[c];
  97.             else pos1=m[c]=len++;
  98.  
  99.             scanf("%s",c);
  100.             if(m[c]) pos2=m[c];
  101.             else pos2=m[c]=len++;
  102.  
  103.             v[pos1].push_back(pos2);
  104.             v[pos2].push_back(pos1);
  105.             scanf("%d",&d);
  106.             cost[pos1][pos2]=d;
  107.             cost[pos2][pos1]=d;
  108.         }
  109.  
  110.         scanf("%s",c);
  111. 		src=m[c];
  112.  
  113. 		scanf("%s",c);
  114.         target=m[c];
  115.  
  116.         prim(src,target);
  117.         int temp_cost=100000;
  118.         while(target!=src)
  119.         {
  120. //			cout<<target<<endl;
  121. 			temp=cost[target][parent[target]];
  122. 			if(temp_cost>temp) temp_cost=temp;
  123. 			target=parent[target];
  124. 		}
  125. 		printf("Scenario #%d\n%d tons\n\n",caseno++,temp_cost);
  126.  
  127. 		memset(v,0,sizeof(v));
  128. 		m.clear();
  129. //		memset(cost,0,sizeof(cost));
  130. //		memset(store,0,sizeof(store));
  131.     }
  132.     return 0;
  133.  
  134. }
  135.  
  136.  
Success #stdin #stdout 0s 3056KB
comments (?)
stdin
copy 
4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
6 7
A B 5
B C 10
A C 3
C D 1
C E 2
C F 4
E F 9
A D
0 0
stdout
copy 
Scenario #1
80 tons

Scenario #2
170 tons

Scenario #3
1 tons
https://ideone.com/JRDg5A
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!