An undirected graph with N vertices and M edges is specified. Vertices are numbered starting from one. Each edge is characterized by its weight and color (red or black). You need to find a path with a minimum total weight from vertex 1 to vertex N. In this case, the path must be interspersed along red and black edges. This means that if the first edge in the path found is red, then the second must be black, the third must be red again, and so on. If the first edge is black, then the second must be red, and so on.

I tried, solved and turned out some algorithm, but it does not always work correctly. Maybe someone will have ideas?

I tried the Dijkstra algorithm. At the same time, for each vertex I kept the color of the edge that I hit on this vertex and then if I can get to this vertex by the red and black edges, then I checked this vertex 2 times. And then I just went through all the vertices in which you can get out of it, and so for each.

It did not work out what exactly I do not know. Since, in my case, the test goes in the following way: there are 27 tests (which I don’t see). And now I have 20/27. Errors in the code I can not find the code itself

versh.push(0); reddist[0] = 0; blackdist[0] = 0; while (!versh.empty()) { int temp; temp = versh.front(); versh.pop(); for (int l = 0; l < N; l++) { int m = 1; if (ves[temp][l] >= 0) { if (temp != 0) { if (redcolor[temp] != -1) { if (cvet[temp][l] != 0) { blackcolor[l] = cvet[temp][l]; m = 2; } }//цвет вершины в которую пришёл по чёрному чёрный if (blackcolor[temp] != -1) { if (cvet[temp][l] != 1) { redcolor[l] = cvet[temp][l]; m = 3; } }//аналогично только красный } else { if (cvet[temp][l] == 0) { redcolor[l] = 0; m = 3; } else { blackcolor[l] = 1; m = 2; } } if (redcolor[l] != -1 && m == 3) { if (reddist[l] > blackdist[temp] + ves[temp][l]) { reddist[l] = blackdist[temp] + ves[temp][l]; versh.push(l); if (l == N - 1) { if (res > reddist[l]) res = reddist[l]; } } } if (blackcolor[l] != -1 && m == 2) { if (blackdist[l] > reddist[temp] + ves[temp][l]) { blackdist[l] = reddist[temp] + ves[temp][l]; versh.push(l); if (l == N - 1) { if (res > blackdist[l]) res = blackdist[l]; } } } } m = 1; } }
  • one
    Add to the question - what algorithm did you try that didn't work out? - Kromster
  • A well-known task is dynamic programming — what's the problem? - Alexander Muksimov
  • "It did not work out what specifically I do not know." - even if you do not know, how do we know? - Kromster
  • So maybe tell me some solution. How best to implement the same Dijkstra algorithm for this task - Artem
  • @ Artem supplemented the answer - Kromster

2 answers 2

You need a Dijkstra algorithm (Dijkstra) with a small addition. The complexity of the algorithm is how to handle re-arrival at the vertex along the edge of a "different" color. It turns out at the top you need to keep a couple of ways (weights) - on the black and on the red "parish", and build a further way starting from them.

If you came by the "same" color, then simply replace the value with the best.

What information is stored at the top?

  • the red top from which you came
  • accumulated red weight
  • the black top from which you came
  • accumulated black weight
  • I understand that Dijkstra, but the fact is that if I came to this peak in two ways (red and black), then from it I can go further to any peak. And it is implemented, but does not pass the tests - Artem
  • Something that may not work - we get to some peak, say, along the black edge, and there is already a smaller path along the red. But at the same time we cannot reject our black path, because it is not clear what will happen next when going from this peak ... It seems to me that all paths starting from the red edge should be considered separately and paths starting from black, and then compare the minimum ... Is this an open system, where do you test? I mean, strangers can climb? If yes - do not give the URL? - Harry
  • So how do you keep these colors? For example, there is a vertex, I came to it in a red and black edge, and this vertex is connected to 4 more vertices. Since I come to this peak in two different ways, I can go further to any of these 4. But how can I do this? - Artem
  • No, the system, unfortunately, is closed. But if you're interested, I can give you an account - Artem
  • @Harry thanks for suggesting! Now, it seems, everything is taken into account. - Kromster

The solution was simple. It turns out in this case, be sure to consider that we have a multigraph and there are loops. That's actually part of the code. So we read:

  while (fin >> i) { info.push_back(i); } for (int j = 0; j < info.size(); j++) { if (j % 4 == 2) { if (ves[info[j - 2] - 1][info[j - 1] - 1] == -1) { ves[info[j - 2] - 1][info[j - 1] - 1] = info[j]; ves[info[j - 1] - 1][info[j - 2] - 1] = info[j]; cvet[info[j - 2] - 1][info[j - 1] - 1] = info[j + 1]; cvet[info[j - 1] - 1][info[j - 2] - 1] = info[j + 1]; } else { if (cvet[info[j - 2] - 1][info[j - 1] - 1] != info[j + 1]) { if (tves[info[j - 2] - 1][info[j - 1] - 1] == -1) { tves[info[j - 2] - 1][info[j - 1] - 1] = info[j]; tves[info[j - 1] - 1][info[j - 2] - 1] = info[j]; tcvet[info[j - 2] - 1][info[j - 1] - 1] = info[j + 1]; tcvet[info[j - 1] - 1][info[j - 2] - 1] = info[j + 1]; } else { if (tves[info[j - 2] - 1][info[j - 1] - 1] > info[j]) { tves[info[j - 2] - 1][info[j - 1] - 1] = info[j]; tves[info[j - 1] - 1][info[j - 2] - 1] = info[j]; } } } if (cvet[info[j - 2] - 1][info[j - 1] - 1] == info[j + 1]) { if (ves[info[j - 2] - 1][info[j - 1] - 1] > info[j]) { ves[info[j - 2] - 1][info[j - 1] - 1] = info[j]; ves[info[j - 1] - 1][info[j - 2] - 1] = info[j]; } } } } } А вот алгоритм while (!versh.empty()) { int temp; temp = versh.front(); versh.pop(); for (int l = 0; l < N; l++) { int m = 1, b = 1; if (ves[temp][l] >= 0) { if (temp != 0) { if (redcolor[temp] != -1) { if (cvet[temp][l] == 1) { blackcolor[l] = cvet[temp][l]; m = 2; } if (tcvet[temp][l] == 1) { blackcolor[l] = tcvet[temp][l]; b = 2; } }//цвет вершины в которую пришёл по красному чёрный if (blackcolor[temp] != -1) { if (cvet[temp][l] == 0) { redcolor[l] = cvet[temp][l]; m = 3; } if (tcvet[temp][l] == 0) { redcolor[l] = tcvet[temp][l]; b = 3; } }//аналогично только красный } else { if (cvet[temp][l] == 0) { redcolor[l] = 0; m = 3; } if (tcvet[temp][l] == 1) { blackcolor[l] = 1; b = 2; } if (cvet[temp][l] == 1) { blackcolor[l] = 1; m = 2; } if (tcvet[temp][l] == 0) { redcolor[l] = 0; b = 3; } } if ((redcolor[l] != -1) && (m == 3 || b == 3)) { if (m == 3) { if (reddist[l] > blackdist[temp] + ves[temp][l]) { reddist[l] = blackdist[temp] + ves[temp][l]; versh.push(l); } } if (b == 3) { if (reddist[l] > blackdist[temp] + tves[temp][l]) { reddist[l] = blackdist[temp] + tves[temp][l]; versh.push(l); } } } if ((blackcolor[l] != -1) && (m == 2 || b == 2)) { if (m == 2) { if (blackdist[l] > reddist[temp] + ves[temp][l]) { blackdist[l] = reddist[temp] + ves[temp][l]; versh.push(l); } } if (b == 2) { if (blackdist[l] > reddist[temp] + tves[temp][l]) { blackdist[l] = reddist[temp] + tves[temp][l]; versh.push(l); } } } } m = 1; b = 1; } }