#include #include #include #include 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; } }