e-olymp 2267. Journey

03/06/2016 by Таран Таня

The army of Rzeczpospolita is moving from the city Kostroma to the village Domnino. Two hetmans, Stefan and Konstantin, lead the army.

Stefan procured the roadmap of Kostroma province, and every night he routes the army from one village to the other along some road. Konstantin bought the map of secret trails between villages in advance, and every day he leads the march along the one of such trails. Each hetman asks their guide Ivan Susanin for a route before each march.

The length of each road is indicated on Stefan’s map. So Stefan knows the minimal distance from each village to the Domnino village according to his map. Similarly Konstantin knows the minimal distance from each village to Domnino village along trails on his map.

Ivan Susanin does not want to be disclosed as a secret agent, so each time he chooses a road (for Stefan) or a trail (for Konstantin) so, that the minimal distance to the Domnino village according to the map owned by the asking hetman is strictly decreasing.

Help Ivan to ﬁnd the longest possible route to the Domnino village.

Input

The ﬁrst line contains three integer numbers [latex]n, s[/latex] and [latex]t[/latex] — number of villages in Kostroma province, and numbers of start and Domnino village [latex](2 \le n \le 1000; 1 \le s; t \le n)[/latex]. Villages are numbered from [latex]1[/latex] to [latex]n[/latex]. Start and Domnino villages are distinct.

Two blocks follow, the ﬁrst one describing Stefan’s map, and the second one describing Konstantin’s map.

The first line of each block contains an integer number [latex]m[/latex] — the number of roads/trails between villages [latex](n-1 \le m \le 100000)[/latex]. Each of the following [latex]m[/latex]lines contains three integer numbers [latex]a, b[/latex], and [latex]l[/latex] — describing the road/trail between villages [latex]a[/latex] and [latex]b[/latex] of length [latex]l[/latex] [latex](1 \le a, b \le n; 1 \le l \le 10^6)[/latex].

Rzeczpospolita army can move in any direction along a road or a trail. It’s guaranteed that one can travel from any village to any other using each of the maps. The army starts its movement in the evening from the village number and moves one road each night and one trail each day.

Output

Output the total length of the longest route that Ivan Susanin can arrange for Rzeczpospolita army before reaching the Domnino village (along the roads and trails). If Ivan Susanin can route the army forever without reaching the Domnino village, output the number «[latex]-1[/latex]».

Tests

№	Input	Output
1	5 1 5 5 1 2 2 1 4 2 2 3 1 3 4 1 5 3 1 4 1 2 2 2 4 2 2 3 1 2 5 2	-1
2	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	20

Algorithm

The problem has been resolved together with Sploshnov Kirill.

So, we are dealing with a rather cumbersome task for the graphs, therefore we analyze it consistently. To get started we define the data structure

struct Route {
    int color;
    unsigned int to; 
    unsigned int length;
};

struct Route {

int color;

unsigned int to;

unsigned int length;

};

because dealing with the routes and subsequently, we will have to color our edges. For convenience, we don’t think about two maps as about different graphs, and can establish one graph, where edges of each map are painted in a different color.
For example edges of first map color in RED, and the other in BLUE. Then select the first map is equivalent to passing by red edges, or blue otherwise. In this way, route, that we are looking for, should be based on the successively alternating colors of the edges.
Proceed directly to the solution.
From the condition is understandable, that each hetman knows the shortest path to the final village. This data will be needed for us too, so for each map (edges of the same color) use Dijkstra’s algorithm and find the shortest path from each vertex to the target. (Function void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color); ). We need absolutely standard Dijkstra’s algorithm with the only difference that the edges of the opposite color aren’t available. You can learn more about Dijkstra’s algorithm in the sources of information listed at the end of the article.
Continue analyzing the condition, we understand, that we can’t pass over the edges so, that the shortest distance to the final vertex increased. This will help us to simplify the graph, and significantly reduce the number of possible variants of passage, namely, any bidirectional edge will be either removed completely or strictly directed. Then, passing on to the edges of the same color in each map, if it doesn’t satisfy the specified condition coloring it as DELETED. (Function void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color); ).
Now we can get started with the search for the longest route. There are two options: either there is the longest path, or we can walk along the edges infinitely, if it does not contradict the statement of the problem, that is, in the combined of two maps graph there is a cycle. So we organize checks on acyclic. Now we have the right to pass along the edges only alternating colors at each step. In order to find a cycle, we use vertex coloring, and will explore the graph until we try to treat already colored vertex or not conclude that it is acyclic. (Function bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color); ). This algorithm can be obtained after detailed acquaintance with the usual cycle searching algorithm (reference to the source is located at the end of the article). If we find any loop in this graph, then our job is over and we should just output «[latex]-1[/latex]».
Otherwise, make sure that the graph is acyclic, we are looking for the longest route. As our graph has been simplified and has no cycles, and all edges are directed, then the task of finding this way becomes computationally simple. For this declaring an array of longest distance dynamically, along the way memorizing the already calculated values, sequentially find the maximum length of the route until we arrive at the finish village. (Function int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) ). This will be the answer to the task.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <vector>
#include <iostream>
#include <algorithm>
#define DELETED -1
#define WHITE 0
#define GREY 1
#define BLACK 2
#define RED 3
#define BLUE 4
#define MAX_INT 2147483647
using namespace std;
 
//  The structure, describing the roads/trails 
struct Route {
    int color;
    unsigned int to; 
    unsigned int length;
    //  Constructor by destination, length and color of edge
    Route(unsigned int to, unsigned int length, int color) {
        this->to = to;
        this->color = color;
        this->length = length;
    }
};
 
/*  
    Function implements ordinary Dijkstra's algorithm (for all edges of the same color)
    As a result, an array of distances filled with the minimum distance to each vertex
*/
void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {
    int vertexWithMinDist = -1;
    bool* passed = new bool[quantityOfAllVertices];
    fill(passed, passed + quantityOfAllVertices, false);
    fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);
    distancesInColoredGraph[finishVertex] = 0;
    for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {
        vertexWithMinDist = -1;
        for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {
            if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {
                vertexWithMinDist = indexOfVertex;
            }
        }
        passed[vertexWithMinDist] = true;
        for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {
            if (graph[vertexWithMinDist][adjacentVertex].color == color 
                && graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {
                distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];
            }
        }
    }
}
 
//  Function indicates the edges we don't need as deleted (because we can't pass them)
void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {
    //  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
    for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {
        for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {
            if (graph[indexOfCurrentVertex][adjacentVertex].color == color 
                && distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {
                graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;
            }
        }
    }
}
 
//  Function determines whether you can go in cycle by the edges of alternating colors 
bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {
    bool answer = false;
    //  Note processing vertex
    if (color == RED) {
        passedInRedGraph[currentVertex] = GREY;
    } else {
        passedInBlueGraph[currentVertex] = GREY;
    }
    /*
        Implement ordinary checking on cycle, by coloring graph
        Treat until we don't determine it is acyclic or try to color vertex that is already colored
        We should take into account the fact, that each time we alternate the color of the edges
    */
    for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {
        if (graph[currentVertex][adjacentVertex].color == color) {
            if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY 
                || color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {
                answer = true;
            }
            if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
                if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {
                    answer = true;
                }
            } else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
                if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {
                    answer = true;
                }
            }
        }
    }
    //  Note processed vertex
    if (color == RED) {
        passedInRedGraph[currentVertex] = BLACK;
    } else {
        passedInBlueGraph[currentVertex] = BLACK;
    }
    return answer;
}
 
//  Function determines whether there is a suitable cycle in the graph
bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {
    int* passedInRedGraph = new int[quantityOfAllVertices];
    int* passedInBlueGraph = new int[quantityOfAllVertices];
    fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);
    fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);
    return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);
}
 
//  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
int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {
    //  Return the length of the path from the current vertex, if it's found already
    if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {
        return maxDistancesInRedGraph[currentVertex];
    }
    if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {
        return maxDistancesInBlueGraph[currentVertex];
    }
    int maxDistance = -1;   //  Initially, we consider the longest path by any negative number
    for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {
        /*
            Recursively find the longest path to the finish vertex
            We should take into account the fact, that each time we alternate the color of the edges
        */
        if (graph[currentVertex][adjacentVertex].color == color) {
            int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to, 
                color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;
            maxDistance = max(maxDistance, currentMaxDistance);
        }
    }
    //  Remember the results received in the process of bypassing for later use
    if (color == RED) {
        maxDistancesInRedGraph[currentVertex] = maxDistance;
    } else {
        maxDistancesInBlueGraph[currentVertex] = maxDistance;
    }
    return maxDistance;
}
 
//  Function returns the longest path in the graph from the start vertex to the finish
int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {
    int* maxDistancesInRedGraph = new int[quantityOfAllVertices];
    int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];
    fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);
    fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);
    maxDistancesInRedGraph[finishVertex] = 0;
    maxDistancesInBlueGraph[finishVertex] = 0;
    return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);
}
 
int main() {
    ios::sync_with_stdio(false);
    unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;
    cin >> quantityOfAllVertices >> startVertex >> finishVertex;
    startVertex--; finishVertex--;  //  Shift numbering
    vector<Route>* graph = new vector<Route>[quantityOfAllVertices];    // Stores graph as array of routes for each vertex
    cin >> quantityOfVertices;
    while (quantityOfVertices--) {
        cin >> from >> to >> length;
        from--; to--;   //  Shift numbering
        if (from != to) {   //  Don't read cycles
            // Initially, all roads are bidirectional, add symmetrically
            graph[from].push_back(Route(to, length, RED));
            graph[to].push_back(Route(from, length, RED));
        }
    }
    cin >> quantityOfVertices;
    while (quantityOfVertices--) {
        cin >> from >> to >> length;
        from--; to--; 
        if (from != to) {
            graph[from].push_back(Route(to, length, BLUE));
            graph[to].push_back(Route(from, length, BLUE));
        }
    }
    int* distancesInRedGraph = new int[quantityOfAllVertices];  //  Shortest distances from each vertex to the final by red edges
    int* distancesInBlueGraph = new int[quantityOfAllVertices]; //  Shortest distances from each vertex to the final by blue edges
    djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED);     //  Find and remember the shortest path by the red edges
    djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE);   //  Find and remember the shortest path by the blue edges
    simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED);   //  Note red edges which we can't pass, so that later they don't take into account
    simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); //  Note blue edges which we can't pass, so that later they don't take into account
    cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

#include <vector>

#include <iostream>

#include <algorithm>

#define DELETED -1

#define WHITE 0

#define GREY 1

#define BLACK 2

#define RED 3

#define BLUE 4

#define MAX_INT 2147483647

using namespace std;

// The structure, describing the roads/trails

struct Route {

int color;

unsigned int to;

unsigned int length;

// Constructor by destination, length and color of edge

Route(unsigned int to, unsigned int length, int color) {

this->to = to;

this->color = color;

this->length = length;

}

};

Function implements ordinary Dijkstra's algorithm (for all edges of the same color)

As a result, an array of distances filled with the minimum distance to each vertex

void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {

int vertexWithMinDist = -1;

bool* passed = new bool[quantityOfAllVertices];

fill(passed, passed + quantityOfAllVertices, false);

fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);

distancesInColoredGraph[finishVertex] = 0;

for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {

vertexWithMinDist = -1;

for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {

if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {

vertexWithMinDist = indexOfVertex;

}

passed[vertexWithMinDist] = true;

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {

if (graph[vertexWithMinDist][adjacentVertex].color == color

&& graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {

distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];

}

// Function indicates the edges we don't need as deleted (because we can't pass them)

void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {

// 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

for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {

if (graph[indexOfCurrentVertex][adjacentVertex].color == color

&& distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {

graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;

}

// Function determines whether you can go in cycle by the edges of alternating colors

bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {

bool answer = false;

// Note processing vertex

if (color == RED) {

passedInRedGraph[currentVertex] = GREY;

} else {

passedInBlueGraph[currentVertex] = GREY;

}

Implement ordinary checking on cycle, by coloring graph

Treat until we don't determine it is acyclic or try to color vertex that is already colored

We should take into account the fact, that each time we alternate the color of the edges

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {

if (graph[currentVertex][adjacentVertex].color == color) {

if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY

|| color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {

answer = true;

}

if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {

if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {

answer = true;

}

} else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {

if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {

answer = true;

}

// Note processed vertex

if (color == RED) {

passedInRedGraph[currentVertex] = BLACK;

} else {

passedInBlueGraph[currentVertex] = BLACK;

}

return answer;

}

// Function determines whether there is a suitable cycle in the graph

bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {

int* passedInRedGraph = new int[quantityOfAllVertices];

int* passedInBlueGraph = new int[quantityOfAllVertices];

fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);

fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);

return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);

}

// 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

int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {

// Return the length of the path from the current vertex, if it's found already

if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {

return maxDistancesInRedGraph[currentVertex];

}

if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {

return maxDistancesInBlueGraph[currentVertex];

}

int maxDistance = -1; // Initially, we consider the longest path by any negative number

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {

Recursively find the longest path to the finish vertex

We should take into account the fact, that each time we alternate the color of the edges

if (graph[currentVertex][adjacentVertex].color == color) {

int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to,

color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;

maxDistance = max(maxDistance, currentMaxDistance);

}

// Remember the results received in the process of bypassing for later use

if (color == RED) {

maxDistancesInRedGraph[currentVertex] = maxDistance;

} else {

maxDistancesInBlueGraph[currentVertex] = maxDistance;

}

return maxDistance;

}

// Function returns the longest path in the graph from the start vertex to the finish

int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {

int* maxDistancesInRedGraph = new int[quantityOfAllVertices];

int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];

fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);

fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);

maxDistancesInRedGraph[finishVertex] = 0;

maxDistancesInBlueGraph[finishVertex] = 0;

return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);

}

int main() {

ios::sync_with_stdio(false);

unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;

cin >> quantityOfAllVertices >> startVertex >> finishVertex;

startVertex--; finishVertex--; // Shift numbering

vector<Route>* graph = new vector<Route>[quantityOfAllVertices]; // Stores graph as array of routes for each vertex

cin >> quantityOfVertices;

while (quantityOfVertices--) {

cin >> from >> to >> length;

from--; to--; // Shift numbering

if (from != to) { // Don't read cycles

// Initially, all roads are bidirectional, add symmetrically

graph[from].push_back(Route(to, length, RED));

graph[to].push_back(Route(from, length, RED));

}

cin >> quantityOfVertices;

while (quantityOfVertices--) {

cin >> from >> to >> length;

from--; to--;

if (from != to) {

graph[from].push_back(Route(to, length, BLUE));

graph[to].push_back(Route(from, length, BLUE));

}

int* distancesInRedGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by red edges

int* distancesInBlueGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by blue edges

djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED); // Find and remember the shortest path by the red edges

djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE); // Find and remember the shortest path by the blue edges

simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED); // Note red edges which we can't pass, so that later they don't take into account

simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); // Note blue edges which we can't pass, so that later they don't take into account

cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;

return 0;

}

Related Images:

e-olymp 2906. Can you answer these queries — 1

23/05/2016 by Таран Таня

You are given an integer sequence.

[latex]a_1, a_2, \ldots, a_n (|a_i| \le 15007, 1 \le n \le 50000)[/latex].

A query is defined as follows:

[latex]Query(x, y) = MAX (a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y)[/latex]

Given [latex]m[/latex] queries, your program must output the results of these queries.

Input

The first line contains the integer [latex]n[/latex]. In the second line [latex]n[/latex] integers of the sequence are given. The third line contains the integer [latex]m[/latex]. Then [latex]m[/latex] lines follow, where line [latex]i[/latex] contains two numbers [latex]x_i[/latex] and [latex]y_i[/latex].

Output

Print the results of the [latex]m[/latex] queries, one query per line.

Tests

№	Input	Output
1	3 -1 2 3 1 1 2	2
2	5 1 2 3 4 5 1 1 5	15
3	5 -1 -2 -3 -4 -5 1 1 5	-1
4	8 1 2 -3 -2 10 1 -15 7 4 1 1 3 4 3 6 1 8	1 -2 11 11
5	9 1 -2 3 -4 5 -6 7 -8 9 3 1 9 2 8 2 4	9 7 3

Algorithm

After analyzing the condition of the problem, we can understand that we need on a given segments of array to find subsegment with a maximum amount. We can solve this task by using segment tree, but before this we should modify it a bit. Create a structure of which our tree consists:

struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
}

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

}

That is, in each vertex of tree we store [latex]4[/latex] values:

the answer to the task for the current subsegment
the maximum amount among all prefixes
the maximum amount among all suffixes
the sum on the segment

First we need to get the values in the leaves. It’s simple enough all [latex]4[/latex] fields take the value of the number, that corresponds to this leaf. Now, having values in the leaves, we need to learn how to get the values in parent. For this we use the function Node mergeNodes(Node leftChild, Node rightChild), which assign to parent’s fields such values:

Answer in the parent equal to the answer in the right or the left child (means that the best subsegment of the current node is entirely in the left or right child), or the maximum amount of the maximum suffix in the left child and the maximum prefix in the right child (which means that it is partially is in the left child and partially is in the right child).
The maximum amount of the parent on prefix is equal to the maximum prefix of left child or sum on segment of left child and maximum prefix of right child.
The maximum amount of the parent on suffix is equal to the maximum suffix of right child or sum on segment of right child and maximum suffix of right child.
Amount on segment of the parent is equal to the sum on segment of left child and sum on segment of right child.

Now, with all the auxiliary functions for working with a built data structure, we need only to construct a tree and learn to get an answer on it.
We need two more functions:

void build(int *base, Node *tree, int currentNode, int left, int right) — recursive construction of a tree from the leaves to the root by initial sequence numbers.
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) — as in the usual tree segments we get an answer going down by the tree, but instead of any associative function (eg sum or maximum) we execute the merger of nodes described earlier. Resulting node will store an answer corresponding to a given in the query segment.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <cmath>
#include <iostream>
#define INF -15008
using namespace std;

//  Function, that teturn lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {                    
    int answer;
    answer = 1 << (int)(log2((double)number - 1) + 1);
    return answer;
}

//  The structure describing the components from which consists a tree
struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
    //  Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment
    Node() {
        answer = INF;
        sumOnPrefix = INF;
        sumOnSuffix = INF;
        sumOnSegment = INF;
    }
    // Constructs a node by a value of the initial sequence of numbers
    Node(int value) {
        answer = value;
        sumOnPrefix = value;
        sumOnSuffix = value;
        sumOnSegment = value;
    }
};

//  Function, that merges two nodes (childs) and returns new node (parent)
Node mergeNodes(Node leftChild, Node rightChild) {
    Node crossedNode;
    crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;
    crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);
    crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);
    crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));
    return crossedNode;
}

//  Function, that building a tree recursive
void build(int *base, Node *tree, int currentNode, int left, int right) {
    if (left == right) {
        tree[currentNode] = Node(base[left]);
    } else {
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        build(base, tree, leftChild, left, middle);
        build(base, tree, leftChild + 1, middle + 1, right);
        // Use the previously described function to get the value of parent by his children
        tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
    }
}

//  Function, that return node, storing the answer to the problem (subsegment with a maximum amount)
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
    if (left == leftBorder && right == rightBorder) {
        return tree[currentNode];
    }
    int leftChild = 2 * currentNode;
    int middle = (left + right) / 2;
    if (rightBorder <= middle) {
        return answer(tree, leftChild, left, middle, leftBorder, rightBorder);
    }
    if (leftBorder > middle) {
        return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
    }
    return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),
        answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));
}

int main() {
    std::ios::sync_with_stdio(false);
    unsigned int quantityOfNumbers;
    cin >> quantityOfNumbers;
    int *base = new int[quantityOfNumbers];     //  A given sequence of numbers 
    for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {
        cin >> base[indexOfNumber];
    }
    int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
    Node *tree = new Node[sizeOfTree];
    build(base, tree, 1, 0, quantityOfNumbers - 1);
    unsigned int quantityOfRequests;
    cin >> quantityOfRequests;
    for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
        unsigned int leftBorder, rightBorder;
        cin >> leftBorder >> rightBorder;
        cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;
    }
    return 0;
}

#include <cmath>

#include <iostream>

#define INF -15008

using namespace std;

// Function, that teturn lowest power of 2, bigger than a given number

int lowestBiggerPowOf2Than(int number) {

int answer;

answer = 1 << (int)(log2((double)number - 1) + 1);

return answer;

}

// The structure describing the components from which consists a tree

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

// Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment

Node() {

answer = INF;

sumOnPrefix = INF;

sumOnSuffix = INF;

sumOnSegment = INF;

}

// Constructs a node by a value of the initial sequence of numbers

Node(int value) {

answer = value;

sumOnPrefix = value;

sumOnSuffix = value;

sumOnSegment = value;

}

};

// Function, that merges two nodes (childs) and returns new node (parent)

Node mergeNodes(Node leftChild, Node rightChild) {

Node crossedNode;

crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;

crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);

crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);

crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));

return crossedNode;

}

// Function, that building a tree recursive

void build(int *base, Node *tree, int currentNode, int left, int right) {

if (left == right) {

tree[currentNode] = Node(base[left]);

} else {

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

build(base, tree, leftChild, left, middle);

build(base, tree, leftChild + 1, middle + 1, right);

// Use the previously described function to get the value of parent by his children

tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);

}

// Function, that return node, storing the answer to the problem (subsegment with a maximum amount)

Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {

if (left == leftBorder && right == rightBorder) {

return tree[currentNode];

}

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

return answer(tree, leftChild, left, middle, leftBorder, rightBorder);

}

if (leftBorder > middle) {

return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);

}

return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),

answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));

}

int main() {

std::ios::sync_with_stdio(false);

unsigned int quantityOfNumbers;

cin >> quantityOfNumbers;

int *base = new int[quantityOfNumbers]; // A given sequence of numbers

for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {

cin >> base[indexOfNumber];

}

int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);

Node *tree = new Node[sizeOfTree];

build(base, tree, 1, 0, quantityOfNumbers - 1);

unsigned int quantityOfRequests;

cin >> quantityOfRequests;

for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {

unsigned int leftBorder, rightBorder;

cin >> leftBorder >> rightBorder;

cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;

}

return 0;

}

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: maximum

e-olymp 2267. Journey

Input

Output

Tests

Algorithm

Code

Links

Related Images:

e-olymp 2906. Can you answer these queries — 1

Input

Output

Tests

Algorithm

Code

Links

Related Images: