1. #include <vector>
2. #include <iostream>
3. #include <algorithm>
4. #define DELETED -1
5. #define WHITE 0
6. #define GREY 1
7. #define BLACK 2
8. #define RED 3
9. #define BLUE 4
10. #define MAX_INT 2147483647
11. using namespace std;
12.
13. // The structure, describing the roads/trails
14. struct Route {
15. int color;
16. unsigned int to;
17. unsigned int length;
18. // Constructor by destination, length and color of edge
19. Route(unsigned int to, unsigned int length, int color) {
20. this->to = to;
21. this->color = color;
22. this->length = length;
23. }
24. };
25.
26. /*
27.   Function implements ordinary Dijkstra's algorithm (for all edges of the same color)
28.   As a result, an array of distances filled with the minimum distance to each vertex
29. */
30. void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {
31. int vertexWithMinDist = -1;
32. bool* passed = new bool[quantityOfAllVertices];
33. fill(passed, passed + quantityOfAllVertices, false);
34. fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);
35. distancesInColoredGraph[finishVertex] = 0;
36. for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {
37. vertexWithMinDist = -1;
38. for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {
39. if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {
40. vertexWithMinDist = indexOfVertex;
41. }
42. }
43. passed[vertexWithMinDist] = true;
44. for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {
45. if (graph[vertexWithMinDist][adjacentVertex].color == color
46. && graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {
48. }
49. }
50. }
51. }
52.
53. // Function indicates the edges we don't need as deleted (because we can't pass them)
54. void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {
55. // Note as DELETED routes in which the minimum distance to finish vertex increases, cause we can't walk them on the strength of problem's condition
56. for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {
57. for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {
58. if (graph[indexOfCurrentVertex][adjacentVertex].color == color
59. && distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {
60. graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;
61. }
62. }
63. }
64. }
65.
66. // Function determines whether you can go in cycle by the edges of alternating colors
67. bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {
68. bool answer = false;
69. // Note processing vertex
70. if (color == RED) {
71. passedInRedGraph[currentVertex] = GREY;
72. } else {
73. passedInBlueGraph[currentVertex] = GREY;
74. }
75. /*
76.   Implement ordinary checking on cycle, by coloring graph
77.   Treat until we don't determine it is acyclic or try to color vertex that is already colored
78.   We should take into account the fact, that each time we alternate the color of the edges
79.   */
80. for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {
81. if (graph[currentVertex][adjacentVertex].color == color) {
82. if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY
83. || color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {
84. answer = true;
85. }
86. if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
87. if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {
88. answer = true;
89. }
90. } else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
91. if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {
92. answer = true;
93. }
94. }
95. }
96. }
97. // Note processed vertex
98. if (color == RED) {
99. passedInRedGraph[currentVertex] = BLACK;
100. } else {
101. passedInBlueGraph[currentVertex] = BLACK;
102. }
104. }
105.
106. // Function determines whether there is a suitable cycle in the graph
107. bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {
108. int* passedInRedGraph = new int[quantityOfAllVertices];
109. int* passedInBlueGraph = new int[quantityOfAllVertices];
110. fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);
111. fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);
112. return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);
113. }
114.
115. // Function determines the longest path in the graph by the edges of alternating colors, by finding and memorizing the maximum path to each of the vertices
116. int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {
117. // Return the length of the path from the current vertex, if it's found already
118. if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {
119. return maxDistancesInRedGraph[currentVertex];
120. }
121. if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {
122. return maxDistancesInBlueGraph[currentVertex];
123. }
124. int maxDistance = -1; // Initially, we consider the longest path by any negative number
125. for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {
126. /*
127.   Recursively find the longest path to the finish vertex
128.   We should take into account the fact, that each time we alternate the color of the edges
129.   */
130. if (graph[currentVertex][adjacentVertex].color == color) {
131. int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to,
132. color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;
133. maxDistance = max(maxDistance, currentMaxDistance);
134. }
135. }
136. // Remember the results received in the process of bypassing for later use
137. if (color == RED) {
138. maxDistancesInRedGraph[currentVertex] = maxDistance;
139. } else {
140. maxDistancesInBlueGraph[currentVertex] = maxDistance;
141. }
142. return maxDistance;
143. }
144.
145. // Function returns the longest path in the graph from the start vertex to the finish
146. int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {
147. int* maxDistancesInRedGraph = new int[quantityOfAllVertices];
148. int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];
149. fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);
150. fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);
151. maxDistancesInRedGraph[finishVertex] = 0;
152. maxDistancesInBlueGraph[finishVertex] = 0;
153. return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);
154. }
155.
156. int main() {
157. ios::sync_with_stdio(false);
158. unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;
159. cin >> quantityOfAllVertices >> startVertex >> finishVertex;
160. startVertex--; finishVertex--; // Shift numbering
161. vector<Route>* graph = new vector<Route>[quantityOfAllVertices]; // Stores graph as array of routes for each vertex
162. cin >> quantityOfVertices;
163. while (quantityOfVertices--) {
164. cin >> from >> to >> length;
165. from--; to--; // Shift numbering
166. if (from != to) { // Don't read cycles
167. // Initially, all roads are bidirectional, add symmetrically
168. graph[from].push_back(Route(to, length, RED));
169. graph[to].push_back(Route(from, length, RED));
170. }
171. }
172. cin >> quantityOfVertices;
173. while (quantityOfVertices--) {
174. cin >> from >> to >> length;
175. from--; to--;
176. if (from != to) {
177. graph[from].push_back(Route(to, length, BLUE));
178. graph[to].push_back(Route(from, length, BLUE));
179. }
180. }
181. int* distancesInRedGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by red edges
182. int* distancesInBlueGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by blue edges
183. djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED); // Find and remember the shortest path by the red edges
184. djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE); // Find and remember the shortest path by the blue edges
185. simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED); // Note red edges which we can't pass, so that later they don't take into account
186. simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); // Note blue edges which we can't pass, so that later they don't take into account
187. cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;
188. return 0;
189. }
Success #stdin #stdout 0s 3412KB
stdin
3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10

stdout
20