fork download 
  1. # include <iostream>
  2. # include <cstdio>
  3. # include <queue>
  4. # include <map>
  5. # include <vector>
  6. # include <algorithm>
  7. # include <cstdlib>
  8. # include <limits>
  9. # include <utility>
  10. # include <cstring>
  11. # include <unistd.h>
  12. # include <ctime>
  13. using namespace std;
  14.  
  15. typedef unsigned long long ullong;
  16. typedef long long llong;
  17. class FastIO
  18. {
  19. private:
  20.     const static int READLIMIT  = 1048576;
  21. 	const static int WRITELIMIT = 524288;
  22. 	int ReadIndex, WriteIndex, BufferLength;
  23. 	unsigned char ReadBuffer  [READLIMIT];
  24. 	unsigned char WriteBuffer [WRITELIMIT];
  25. 	unsigned char TempNumber  [25];
  26. 	bool bIsLittleEndian;
  27. 	void Fetch()
  28. 	{
  29. 		if (ReadIndex >= BufferLength)
  30. 		{
  31. 			ReadIndex = 0;
  32. 			BufferLength = fread (ReadBuffer,  1, READLIMIT, stdin);
  33. 		}
  34. 	}
  35. public:
  36. 	FastIO (const char * in = "", const char * out = "")
  37. 	{
  38. 		if (in  != "") freopen (in,  "r", stdin);
  39. 		if (out != "") freopen (out, "w", stdout);
  40. 		ReadIndex = 0; WriteIndex = 0; BufferLength = 0;
  41. 		union
  42. 		{
  43. 			uint32_t i;
  44. 			char c[4];
  45. 		} bint = {0x01020304};
  46. 		bIsLittleEndian = (bint.c[0] == 1);
  47. 	}
  48. 	void SetStreams (const char * in = "", const char * out = "")
  49. 	{
  50. 		if (in  != "") 
  51. 		{
  52. 			freopen (in,  "r", stdin);
  53. 			ReadIndex = BufferLength = 0;
  54. 		}
  55. 		if (out != "")
  56. 		{
  57. 			freopen (out, "w", stdout);
  58. 			WriteIndex = 0;
  59. 		}
  60. 	}
  61. 	bool IsEOF()
  62. 	{
  63. 		Fetch();
  64. 		return (BufferLength == 0);
  65. 	}
  66. 	void Flush(bool ForceFlush = false)
  67. 	{
  68. 		if ((WriteIndex >= WRITELIMIT) || ForceFlush)
  69. 		{
  70. 			fwrite (WriteBuffer, 1, WriteIndex, stdout);
  71. 			WriteIndex = 0;
  72. 		}
  73. 	}
  74. 	void getCString(char * String, int MaxLength, bool bIsSpaceBreaks = true)
  75. 	{
  76. 		bool isDone = false, isFirstDigit = true; int CurrentIndex = 0; unsigned char CurrentChar;
  77. 		while (!isDone || CurrentIndex == MaxLength)
  78. 		{
  79. 			if (ReadIndex >= BufferLength) Fetch();
  80. 			if (BufferLength == 0)
  81. 				isDone = true;
  82. 			else
  83. 			{
  84. 				CurrentChar = ReadBuffer [ReadIndex++];
  85. 				if (isFirstDigit)
  86. 				{
  87. 					if (CurrentChar == 10 || CurrentChar == '\t') continue;
  88. 					isFirstDigit = false;
  89. 				}
  90. 				if (CurrentChar == 10 || CurrentChar == 13 || (bIsSpaceBreaks && CurrentChar == ' ')) isDone = true;
  91. 				else String [CurrentIndex++] = CurrentChar;
  92. 			}
  93. 		}
  94. 		String [CurrentIndex] = 0;
  95. 	}
  96. 	ullong getNumber()
  97. 	{
  98. 		ullong Number = 0;
  99. 		bool isDone = false, isFirstDigit = true;
  100. 		while (!isDone)
  101. 		{
  102. 			if (ReadIndex >= BufferLength) Fetch();
  103. 			if (BufferLength == 0)
  104. 				isDone = true;
  105. 			else
  106. 			{
  107. 				int CurrentChar = ReadBuffer [ReadIndex++];
  108. 				if (isFirstDigit)
  109. 				{
  110. 					if (CurrentChar > 57 || CurrentChar < 48) continue;
  111. 					isFirstDigit = false;
  112. 				}
  113. 				if (CurrentChar > 57 || CurrentChar < 48) isDone = true;
  114. 				else Number = ((Number << 3) + (Number << 1)) + (CurrentChar - '0');
  115. 			}
  116. 		}
  117. 		return Number;
  118. 	}
  119. 	llong getSignedNumber()
  120. 	{
  121. 		llong Number = 0;
  122. 		bool isDone = false, isNegative = false, isFirstChar = true;
  123. 		while (!isDone)
  124. 		{
  125. 			if (ReadIndex >= BufferLength) Fetch();
  126. 			if (BufferLength == 0)
  127. 				isDone = true;
  128. 			else
  129. 			{
  130. 				int CurrentChar = ReadBuffer [ReadIndex++];
  131. 				if (isFirstChar)
  132. 				{
  133. 					if ((CurrentChar > 57 || CurrentChar < 48) && CurrentChar != '-') continue;
  134. 					isNegative = (CurrentChar == '-');
  135. 					isFirstChar = !isFirstChar;
  136. 					if (CurrentChar == '-') continue;
  137. 				}
  138. 				if (CurrentChar > 57 || CurrentChar < 48) isDone = true;
  139. 				else Number = ((Number << 3) + (Number << 1)) + (CurrentChar - '0');
  140. 			}
  141. 		}
  142. 		return (isNegative && Number?-Number:Number);
  143. 	}
  144. 	void WriteNumber (ullong Number, bool NewLineNeeded = true)
  145. 	{
  146. 		int idx = 0, temp;
  147. 		if (!Number) TempNumber [idx++] = '0';
  148. 		while (Number)
  149. 		{
  150. 			temp = Number % 10;
  151. 			Number /= 10;
  152. 			TempNumber [idx++] = temp + '0';
  153. 		}
  154. 		TempNumber [idx--] = '\0';
  155. 		for (int i = idx; i > (idx - i); i--)
  156. 		{
  157. 			temp = TempNumber [i];
  158. 			TempNumber [i] = TempNumber[idx - i];
  159. 			TempNumber[idx - i] = temp;
  160. 		}
  161. 		idx++;
  162. 		for (int i = 0; i < idx; i++)
  163. 		{
  164. 			if (WriteIndex >= WRITELIMIT && WriteIndex) Flush();
  165. 			WriteBuffer [WriteIndex++] = TempNumber [i];
  166. 		}
  167. 		if (NewLineNeeded)
  168. 		{
  169. 			if (WriteIndex >= WRITELIMIT && WriteIndex) Flush();
  170. 			WriteBuffer [WriteIndex++] = '\n';
  171. 		}
  172. 	}
  173. 	void WriteSignedNumber (llong Number, bool NewLineNeeded = true)
  174. 	{
  175. 		int idx = 0, temp; bool isNegative = false;
  176. 		if (Number < 0)
  177. 		{
  178. 			isNegative = true;
  179. 			Number = -Number;
  180. 		}
  181. 		if (!Number) TempNumber [idx++] = '0';
  182. 		while (Number)
  183. 		{
  184. 			temp = Number % 10;
  185. 			Number /= 10;
  186. 			TempNumber [idx++] = temp + '0';
  187. 		}
  188. 		TempNumber [idx--] = '\0';
  189. 		for (int i = idx; i > (idx - i); i--)
  190. 		{
  191. 			temp = TempNumber [i];
  192. 			TempNumber [i] = TempNumber[idx - i];
  193. 			TempNumber[idx - i] = temp;
  194. 		}
  195. 		idx++;
  196. 		if (isNegative)
  197. 		{
  198. 			if (WriteIndex >= WRITELIMIT && WriteIndex) Flush();
  199. 			WriteBuffer [WriteIndex++] = '-';
  200. 		}
  201. 		for (int i = 0; i < idx; i++)
  202. 		{
  203. 			if (WriteIndex >= WRITELIMIT && WriteIndex) Flush();
  204. 			WriteBuffer [WriteIndex++] = TempNumber [i];
  205. 		}
  206. 		if (NewLineNeeded)
  207. 		{
  208. 			if (WriteIndex >= WRITELIMIT && WriteIndex) Flush();
  209. 			WriteBuffer [WriteIndex++] = '\n';
  210. 		}
  211. 	}
  212. 	void WriteCString (const char * String, int MaxLength = 0, bool NewLineNeeded = true)
  213. 	{
  214. 		if (MaxLength == 0) MaxLength = strlen (String);
  215. 		for (int i = 0; i < MaxLength; i++)
  216. 		{
  217. 			if (WriteIndex >= WRITELIMIT && WriteIndex) Flush();
  218. 			WriteBuffer [WriteIndex++] = String [i];
  219. 		}
  220. 		if (NewLineNeeded)
  221. 		{
  222. 			if (WriteIndex >= WRITELIMIT && WriteIndex) Flush();
  223. 			WriteBuffer [WriteIndex++] = '\n';
  224. 		}
  225. 	}
  226. };
  227.  
  228. const ullong MAXIMUM = numeric_limits <ullong>::max();
  229. vector <pair <int, ullong> > Weights [10001];
  230. pair <char [12], int> CityMap [10001];
  231. ullong Distances [10001];
  232. struct FindGreaterObject
  233. {
  234. 	bool operator () (pair <int, ullong > & A, pair <int, ullong > & B) const
  235. 	{
  236. 		return A.second > B.second;
  237. 	}
  238. };
  239. priority_queue <pair <int, ullong>, vector <pair <int, ullong> >, FindGreaterObject > Q;
  240. int ComparePairs (const void * first, const void * second)
  241. {
  242. 	return strcmp (((pair <char [12], int> *)first)->first, ((pair <char [12], int> *)second)->first);
  243. }
  244. int main(int argc, char const *argv[])
  245. {
  246. 	FastIO io;
  247. 	int T, TVertices, TNeighbours, TDistances, NeightbourIndex, Distance, Start = 0, End = 0; char City[12], City1[12];
  248. 	pair <int, ullong> Current;
  249. 	T = io.getNumber();
  250. 	while (T--)
  251. 	{
  252. 		TVertices = io.getNumber();
  253. 		for (int i = 1; i <= TVertices; i++)
  254. 		{
  255. 			io.getCString (CityMap [i-1].first, 11);
  256. 			CityMap [i-1].second = i;
  257. 			TNeighbours = io.getNumber();
  258. 			for (int j = 0; j < TNeighbours; j++)
  259. 			{
  260. 				NeightbourIndex = io.getNumber(); Distance = io.getNumber();
  261. 				Weights [i].push_back (make_pair (NeightbourIndex, Distance));
  262. 			}
  263. 		}
  264. 		qsort (CityMap, TVertices, sizeof (pair <char [12], int>), ComparePairs);
  265. 		TDistances = io.getNumber();
  266. 		for (int i = 0; i < TDistances; i++)
  267. 		{
  268. 			Start = End = -1;
  269. 			io.getCString (City, 11); io.getCString (City1, 11);
  270. 			pair <char [12], int> * CityIndex = (pair <char [12], int> *)bsearch (City, CityMap, TVertices, sizeof (pair <char [12], int>), ComparePairs);
  271. 			Start = CityIndex->second;
  272. 			CityIndex = (pair <char [12], int> *) bsearch (City1, CityMap, TVertices, sizeof (pair <char [12], int>), ComparePairs);
  273. 			End   = CityIndex->second;
  274. 			fill (Distances, Distances + TVertices + 1, MAXIMUM);
  275. 			Distances [Start] = 0;
  276. 			while (!Q.empty()) Q.pop();
  277. 			Q.push (make_pair (Start, 0));
  278. 			while (!Q.empty())
  279. 			{
  280. 				Current = Q.top(); Q.pop();
  281. 				if (Distances [Current.first] < Current.second) continue;
  282. 				if (Current.first == End) break;
  283. 				for (vector <pair <int, ullong> >::iterator it = Weights[Current.first].begin(); it != Weights[Current.first].end(); it++)
  284. 				{
  285. 					ullong AlternateDistance = Distances [Current.first] + (*it).second;
  286. 					if (Distances [(*it).first] > AlternateDistance)
  287. 					{
  288. 						Distances [(*it).first] = AlternateDistance;
  289. 						Q.push (make_pair ((*it).first, AlternateDistance));
  290. 					}
  291. 				}
  292. 			}
  293. 			io.WriteNumber(Distances [End]);
  294. 		}
  295. 	}
  296. 	io.Flush(true);
  297. 	return 0;
  298. }
Success #stdin #stdout 0.02s 4632KB
comments (?)
stdin 
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa
stdout 
3
2
https://ideone.com/7XE0UU
language:
C++ (gcc 8.3)
created:
13 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!