fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define pii pair<int,int>
  3. #define psi pair<string,int>
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7. map< string, ll > M;
  8. map<pair<ll,ll> , ll> m;
  9. map<pair<ll,ll> , ll> :: iterator it1;
  10. map< string, ll > :: iterator it;
  11. inline ll getn()
  12. {
  13. 	ll n=0,c=getchar();
  14. 	while(c<'0' || c>'9')
  15. 	c=getchar();
  16. 		while(c>='0' && c<='9')
  17. 		n=(n<<3)+(n<<1)+c-'0',c=getchar();
  18. 		return n;
  19. }
  20. ll n;
  21. char city[100],str1[100],str2[100];
  22. vector<pair<ll,ll> > v[10001];
  23. ll do_prime(ll index)
  24. {
  25. 	priority_queue<pair<ll,ll> > q;
  26. 	vector<ll> d(n,INT_MAX);
  27. 	vector<bool>check(n,false);
  28. 	vector<ll> par(n,-1);
  29. 	ll a,b,c,weight,i;
  30. 	for( i=0;i<n;i++)
  31. 	{
  32. 		q.push(make_pair(d[i],i));
  33. 	}
  34. 	d[index]=0;
  35.  
  36. 	q.push(make_pair(d[index],index));
  37. 	ll cost=0;
  38. 	ll count=0;
  39. 	while(!q.empty())
  40. 	{
  41. 	      pair<ll,ll> p = q.top();
  42. 	      q.pop();
  43. 	       a=p.second;
  44. 	      check[a]=true;
  45. 	       weight=p.first;
  46. 	       if(a!=0)
  47. 	       {
  48. 		   count+=1;
  49. 	       cost+=m[make_pair(a,par[a])];}
  50. 	       if(count==n-1)
  51. 	       {
  52. 	       	break;
  53. 		   }
  54. 	       //cost+=(*it1).second
  55. 	      for(ll i=0;i<v[a].size();i++)
  56. 	      {
  57.  
  58.  
  59. 	      		 b=v[a][i].first;
  60. 	      		c=v[a][i].second;
  61. 	      		if(!check[b])
  62. 	      		{
  63.  
  64. 	      		if(c+d[a] < d[b])
  65. 	      		{
  66.  
  67. 	      			d[b]=c+d[a];
  68. 	      			q.push(make_pair(d[b],b));
  69. 	      			par[b]=a;
  70. 				}
  71. 			}
  72.  
  73.  
  74. 		  }
  75.  
  76. 	}
  77. 	return cost;
  78. }
  79. int main()
  80. {
  81. 	//std::ios_base::sync_with_stdio(false);
  82. 	ll t,n1,a,b,i,j,ans;
  83. 	t=getn();
  84. 	//string city;
  85. 	while(t--)
  86. 	{
  87. 		M.clear();
  88. 		n=getn();
  89. 		m.clear();
  90. 		for(i=0;i<n;i++)
  91. 		{
  92. 			v[i].clear();
  93. 		}
  94. 		ll index;
  95. 		ll min=INT_MAX;
  96. 		for( i=0;i<n;i++)
  97. 		{
  98.  
  99. 		    scanf("%s",city);//cin>>city;
  100. 			M.insert(psi(city,i));
  101. 			n1=getn();
  102. 			for(j=0;j<n1;j++)
  103. 			{
  104. 				a=getn();
  105. 				b=getn();
  106. 				v[i].push_back(make_pair(a-1,b));
  107. 				m[make_pair(i,a-1)]=b;
  108. 				if(b<min)
  109. 				{
  110. 					min=b;
  111. 					index=i;
  112. 				}
  113. 				//v[a].push_back(make_pair(i,b));
  114. 			}
  115.  
  116. 		}
  117. 	/*	for(ll i=0;i<n;i++)
  118. 		{
  119. 			for(ll j=0;j<v[i].size();j++)
  120. 			{
  121. 				cout<<v[i][j].first<<","<<v[i][j].second<<" ";
  122. 			}
  123. 			cout<<endl;
  124. 		}*/
  125. 	    cout<<do_prime(index)<<endl;
  126.  
  127. 	}
  128. 	return 0;
  129. }
  130.  
Time limit exceeded #stdin #stdout 5s 3224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6GpEDI
language:
C++ (gcc 8.3)
created:
8 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!