помогите
огэ. 4 задание.
ход решения

Ответ:

(см. прикрепленный файл)

Решим задачу, написав программу.

Вот пример кода, который предполагает, что длины путей - это положительные числа, а 0 = пути нет:

#include <iostream>

#include <vector>

#include <queue>

#include <limits>

using namespace std;

#define INF INT_MAX

struct edge {

int u, v;

long long w;

};

using graph = vector<vector<edge>>;

using p_edge = pair<int, long long>;

vector<long long> solve(graph& g, int start) {

int s = g.size();

vector<bool> visited(s, false);

vector<long long> d(s, INF);

d[start] = 0;

priority_queue<p_edge> q;

q.push( {-start, 0} );

while (!q.empty()) {

 p_edge e = q.top();

 q.pop();

 int u = -e.first;

 visited[u] = true;

 for (edge i : g[u]) {

  if (!visited[i.v]) {

   q.push({ -i.v, i.w });

  }

  d[i.v] = min(d[i.v], d[u] + i.w);

 }

}

return d;

}

int main() {

int n, s, r, e;

cout << "Enter amount of graph vertices: ";

cin >> n;

cout << "Enter start vertice: ";

cin >> s;

cout << "Enter end vertice: ";

cin >> e;

cout << "Enter required vertice (-1 if no such): ";

cin >> r;

graph g(n);

cout << "Enter matrix (0 = no path): " << endl;

for (int i = 0; i < n; ++i) {

 for (int j = 0; j < n; ++j) {

  long long w;

  cin >> w;

  if (w > 0) {

   g[i].push_back({ i, j, w });

  }

 }

}

vector<long long> answ1 = solve(g, s - 1);

if (r == -1) {

 if (answ1[e - 1] < INF) {

  cout << "Shortest way from " << s << " to " << e << " is: " << answ1[e - 1] << endl;

 } else {

  cout << "Cannot reach " << e << " from " << s << ". No such path!" << endl;

 }

} else {

 vector<long long> answ2 = solve(g, r - 1);

 if (answ1[r - 1] < INF && answ2[e - 1] < INF) {

  cout << "Shortest way from " << s << " to " << e << " through " << r << " is: " << answ1[r - 1] + answ2[e - 1] << endl;

 } else {

  cout << "Cannot reach " << e << " from " << s << " through " << r << ". No such path!" << endl;

 }

}

cout << endl;

return 0;

}

В результате получим вот такой итог:

Enter amount of graph vertices: 6

Enter start vertice: 1

Enter end vertice: 6

Enter required vertice (-1 if no such): 3

Enter matrix (0 = no path):

0 5 8 4 1 0

5 0 3 0 3 4

8 3 0 2 0 15

4 0 2 0 4 12

1 3 0 4 0 7

0 4 15 12 7 0

Shortest way from 1 to 6 through 3 is: 13

Задание выполнено!