Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdlib.h>
- #include <stdio.h>
- #include <mem.h>
- int *find(int *m, int n);
- inline int abs(int x){return (x < 0) ? -x : x;}
- int start = 0;
- int finish = 0;
- //#define DEBUG
- int main(int argc, char **argv){
- if(argc > 1)
- freopen(argv[1], "r", stdin);
- else
- freopen("in.txt", "r", stdin);
- int n; std::cin >> n >> start >> finish;
- int *matrix = new int[n*n];
- for(int i = 0; i < n*n; i++) std::cin >> matrix[i];
- int *p = find(matrix, n);
- if(p != NULL)
- for(int i = 1; i <= p[0]; i++) std::cout << p[i] << " ";
- else
- std::cout << "No way from start to finish";
- std::cout << std::endl;
- delete p;
- return 0;
- }
- int* find(int *m, int n){
- int q[2*n], vis[n], restore[n];
- unsigned ql = 0, qr = 0;
- for(int i = 0; i < n; i++) vis[i] = -1;
- q[qr++] = start; //q.push(start)
- vis[start] = 0;
- restore[start] = -1;
- while(qr != ql){ //!q.empty()
- int t = q[ql++];
- for(int i = 0; i < n; i++){
- if(m[t *n+ i] && (vis[i] == -1 || vis[i] > vis[t] + m[t *n+ i])){
- std::cout << "|" << i << " ";
- q[qr++] = i;
- vis[i] = m[t *n+ i] + vis[t];
- restore[i] = t;
- }
- }std::cout << std::endl;
- }
- exit: if(vis[finish] == -1)
- return 0;
- else{
- int *p = new int[n+1];
- int r = finish;
- p[0] = 1;
- p[1] = finish;
- do{
- r = restore[r];
- p[++p[0]] = r;
- }while(p[p[0]] != start);
- //for(int i = 1; i <= p[0]; i++) std::cout << p[i] << " ";
- return p;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement