Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include<queue>
- using namespace std;
- #define N 101
- #define INF 1000000
- vector <int> graph[N];
- vector <int >way[N];
- int lenght[N];
- int used[N];
- int n;
- void bfs(int start) {
- queue<int>q;
- q.push(start);
- used[start] = 1;
- while (q.size() != 0) {
- start = q.front();
- q.pop();
- for (int i = 0; i < n; i++) {
- if ( used[i] == 0 && graph[start][i] != -1) {
- q.push(i);
- way[i ].push_back(i);
- used[i] = 1;
- }
- int per = graph[start][i] + lenght[start];
- if (lenght[i] != 0 && graph[start][i] != -1 && lenght[i] > per) {
- lenght[i] = per;
- q.push(i);
- way[i].push_back(i);
- }
- }
- }
- }
- int main() {
- int start, finish;
- cin >> n >> start >> finish;
- for (int j = 0; j < n; j++) {
- for (int i = 0; i < n; i++) {
- int x;
- cin >> x;
- graph[j].push_back(x);
- }
- }
- for (int i = 0; i < n; i++) lenght[i] = INF;
- lenght[start - 1] = 0;
- bfs(start - 1);
- cout << "lenght " << lenght[finish - 1] << "\n";
- cout << start << " ";
- int end = way[].size();
- for (int i = 0; i <= end; i++) cout << way[i].front() + 1 << " ";
- return 0;
- }
Add Comment
Please, Sign In to add comment