Ответы 1
Ответ:
(см. прикрепленный файл)
Решим задачу, написав программу.
Вот пример кода, который предполагает, что длины путей - это положительные числа, а 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
Задание выполнено!
ответы на свои вопросы
вопросы?
