fork download
copy 
  1. 	#include <bits/stdc++.h>
  2. 	using namespace std;
  3. 	#define lli long long int
  4. 	#define lld long double
  5. 	#define nodecnt 100005
  6. 	#define INF (1<<20)
  7. 	#define mod 1000000007
  8. 	inline lli scan( )
  9. 	{
  10. 		register lli n1 = 0;
  11. 		char c;
  12. 		for( c = getchar_unlocked(); c==' ' || c=='\n' || c == '\t'; c = getchar_unlocked());
  13. 		for( ; c > 0x2f && c < 0x3a; c = getchar_unlocked())
  14. 		n1 = (n1 * 10) + (c & 0x0f);
  15. 		return n1;
  16. 	}
  17. 	lld key[nodecnt],x,y;
  18. 	std::vector<pair<lld,lld> > cord;
  19. 	bool donewith[nodecnt];
  20. 	lli nodes,edges,start,dest,p,ans;
  21. 	std::vector<pair<lli,lli> > graph[nodecnt] ;
  22. 	lld eucdist(lli i,lli j)
  23. 	{
  24. 		return ceil(p*sqrt(((cord[i].first-cord[j].first)*(cord[i].first-cord[j].first))+((cord[i].second-cord[j].second)*(cord[i].second-cord[j].second))));
  25. 	}
  26. 	void prims()
  27. 	{
  28. 		ans=0;
  29. 		set<pair<lld,lli> > Q;
  30. 		for(lli i=1;i<=nodes;i++)
  31. 			key[i]=INF,donewith[i]=false,Q.insert(make_pair(key[i],i));
  32.  
  33. 		Q.erase(Q.find(make_pair(key[start],start)));
  34. 		key[start]=0;
  35.  
  36. 		Q.insert(make_pair(key[start],start));
  37. 		while(!Q.empty())
  38. 		{
  39. 			pair<lld,lli> top=*(Q.begin());
  40. 			Q.erase(Q.begin());
  41. 			lli u=top.second;
  42. 			donewith[u]=true;
  43. 			if(u!=start)
  44. 			{
  45. 				ans+=top.first;
  46. 				if(ans>=mod)
  47. 					ans=ans%mod;
  48. 			}		
  49. 			lli size=graph[u].size();
  50. 			for(lli i=0;i<size;i++)
  51. 			{
  52. 				lli v=graph[u][i].first;
  53. 				lld w=graph[u][i].second;
  54. 				if(donewith[v]==false)
  55. 				{	
  56. 					if(key[v]>w)
  57. 					{
  58. 						Q.erase(Q.find(make_pair(key[v],v)));
  59. 						key[v]=w;
  60. 						Q.insert(make_pair(key[v],v));
  61. 					}
  62. 				}
  63. 			}
  64. 		}
  65. 	}
  66. 	int main(int argc, char const *argv[])
  67. 	{
  68. 		lli t;
  69. 		t=scan();
  70. 		for(lli T=1;T<=t;T++)
  71. 		{
  72. 			nodes=scan(),p=scan();
  73. 			for(lli i=1;i<=nodes;i++)
  74. 				graph[i].clear();
  75. 			cord.clear();
  76. 			cord.push_back(make_pair(INF,INF));
  77. 			for(lli i=1;i<=nodes;i++)
  78. 				x=scan(),y=scan(),cord.push_back(make_pair(x,y));
  79. 			sort(cord.begin()+1,cord.end());
  80. 			for(lli i=1;i<nodes;i++)
  81. 			{
  82. 				lld temp=eucdist(i+1,i);
  83. 				graph[i].push_back(make_pair(i+1,temp));
  84. 				graph[i+1].push_back(make_pair(i,temp));
  85. 				for(lli j=i+2;j<=nodes;j++)
  86. 				{
  87. 					lld temp=eucdist(i,j);
  88. 					if(temp<=eucdist(j,j-1)+eucdist(j-1,i))
  89. 					{	
  90. 						graph[i].push_back(make_pair(j,temp));
  91. 						graph[j].push_back(make_pair(i,temp));
  92. 					}
  93. 				}
  94. 			}
  95. 			start=1,ans=0;
  96. 			prims();
  97. 			printf("Scenario #%lld: %lld\n",T,ans);
  98. 		}
  99. 		return 0;
  100. 	}
Success #stdin #stdout 0s 5680KB
comments (?)
stdin
copy 
2

4 1

35 46

29 13

44 0

27 17

3 18

18 0

11 17

2 31
stdout
copy 
Scenario #1: 56
Scenario #2: 631
https://ideone.com/dhKuoe
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!