fork download
copy 
  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]) {
  47.                 distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];
  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.     }
  103.     return answer;
  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
comments (?)
stdin
copy 
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
copy 
20
https://ideone.com/KGNM9o
e-olymp 2267!!!!
language:
C++14 (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!