fork download
copy 
  1. #include<iostream>
  2. #include<iomanip>
  3. #include<cstdlib>
  4. #include<cstdio>
  5. #include<unordered_map>
  6. #include<set>
  7. #include<cmath>
  8. #include<string.h>
  9. #include<string>
  10. #include<map>
  11. #include<math.h>
  12. #include<queue>
  13. #include<unordered_set>
  14. #include<vector>
  15. #include<deque>
  16. #include<stack>
  17. #define MAXSIZE 400
  18. #define oo 1000000000000000000
  19. using namespace std;
  20. unordered_map<long long, string>id;
  21. unordered_map<string, long long>cities;
  22. vector<pair<long long, long long>>v_graph[100008];
  23. string city1, city2;
  24. long long cost, cost1, cost2;
  25. long long adj_matrix[MAXSIZE][MAXSIZE];
  26. long long Floyd_Arr[MAXSIZE][MAXSIZE];
  27. long long n_cities, n_edges;
  28. string ArrCities[MAXSIZE];
  29. map<pair<long long, long long>, vector<long long> > Floyd_Path;
  30. void Input()
  31. {
  32. 	cout << "please enter the number of cities .\n";
  33. 	cin >> n_cities;
  34. 	if (n_cities) cout << "\nPlease Enter the names of the cities \n";
  35.  
  36. 	for (int i = 0; i < n_cities; ++i)
  37. 	{
  38. 		cin >> ArrCities[i];
  39. 		cities[ArrCities[i]] = i;
  40. 		id[i] = ArrCities[i];
  41. 	}
  42. 	cout << "\nEnter the Number Of Edges You Want To ADD  \n";
  43. 	cin >> n_edges;
  44. 	cout << "\nEnter The First City Then The Second City Then The Cost Of the Edge \n";
  45. 	while (n_edges)
  46. 	{
  47. 		cin >> city1 >> city2 >> cost;
  48. 		if (city1 == city2){
  49. 			cout << "\nPlease Enter Different Names For City 1 And City 2 \n";
  50. 			continue;
  51. 		}
  52. 		if (!cities.count(city1)) {
  53. 			cout << "\nCity One Isn't in the Cities You Entered ,Please Enter Valid Names \n";
  54. 			continue;
  55. 		}
  56. 		if (!cities.count(city2)){
  57. 			cout << "\nCity Two Isn't in the Cities You Entered ,Please Enter Valid Names \n";
  58. 			continue;
  59. 		}
  60. 		v_graph[cities[city1]].push_back({ cities[city2], cost });
  61. 		v_graph[cities[city2]].push_back({ cities[city1], cost });
  62. 		n_edges--;
  63. 	}
  64. }
  65. void fill_matrix()
  66. {
  67. 	for (int i = 0; i < n_cities; i++) // initializing the adjacency matrix with infinity except the self edges
  68. 	{
  69. 		for (int j = 0; j < n_cities; j++)
  70. 		{
  71. 			Floyd_Arr[i][j] = -1;          // Floyd_Arr Is used In Printing The Path
  72. 			if (i == j)adj_matrix[i][j] = 0;
  73. 			else
  74. 				adj_matrix[i][j] = oo;
  75. 		}
  76. 	}
  77.  
  78. 	for (int i = 0; i < n_cities; i++)// filling up the adjacency matrix
  79. 	{
  80. 		for (int j = 0; j < v_graph[i].size(); j++)
  81. 		{
  82.  
  83. 			adj_matrix[i][v_graph[i][j].first] = v_graph[i][j].second;
  84. 		}
  85. 	}
  86. }
  87. void Print_Floyd_Path(long long Source, long long Distination)
  88. {
  89. 	if (Floyd_Arr[Source][Distination] == -1)
  90. 	{
  91. 		cout << id[Source] << " " << id[Distination] << "\n";
  92. 		return;
  93. 	}
  94. 	Print_Floyd_Path(Source, Floyd_Arr[Source][Distination]); // Printing All Intermediate Nodes
  95. 	Print_Floyd_Path(Floyd_Arr[Source][Distination], Distination);
  96. }
  97. void Floyed_Warchall(long long i, long long j)
  98. {
  99. 	// The Algorithm works on connected Graphs
  100. 	fill_matrix();
  101. 	for (long long k = 0; k < n_cities; k++) // k Will Act As Intermediate node
  102. 	for (long long i = 0; i < n_cities; i++)// i And j Traverse The Adjacency matrix
  103. 	for (long long j = 0; j < n_cities; j++)
  104. 	{
  105. 		if (adj_matrix[i][k] + adj_matrix[k][j] < adj_matrix[i][j])
  106. 		{
  107. 			adj_matrix[i][j] = adj_matrix[i][k] + adj_matrix[k][j];
  108. 			Floyd_Arr[i][j] = k;  // This Arr is For Printing The Path
  109. 		}
  110. 	}
  111. 	if (adj_matrix[i][j] == oo)
  112. 	{ cout << "There's No Path Between " << id[i] << " And " << id[j] << "\n"; return; }
  113. 	cout << "The Cost Between " << id[i] << " And " << id[j] << "is "<<adj_matrix[i][j]<<"\n";
  114. 	cout << "\n\n";
  115. 	Print_Floyd_Path(i, j);
  116. }
  117. int main()
  118. {
  119. 	Input();
  120.  
  121. 	cin >> city1 >> city2;
  122. 	int i = cities[city1], j = cities[city2];
  123. 	Floyed_Warchall(i, j);
  124. 	//system("pause");
  125. 	return 0;
  126. }
  127.  
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
please enter the number of cities .
https://ideone.com/fwIwl4
language:
C++14 (gcc 8.3)
created:
6 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!