- 001
- 002
- 003
- 004
- 005
- 006
- 007
- 008
- 009
- 010
- 011
- 012
- 013
- 014
- 015
- 016
- 017
- 018
- 019
- 020
- 021
- 022
- 023
- 024
- 025
- 026
- 027
- 028
- 029
- 030
- 031
- 032
- 033
- 034
- 035
- 036
- 037
- 038
- 039
- 040
- 041
- 042
- 043
- 044
- 045
- 046
- 047
- 048
- 049
- 050
- 051
- 052
- 053
- 054
- 055
- 056
- 057
- 058
- 059
- 060
- 061
- 062
- 063
- 064
- 065
- 066
- 067
- 068
- 069
- 070
- 071
- 072
- 073
- 074
- 075
- 076
- 077
- 078
- 079
- 080
- 081
- 082
- 083
- 084
- 085
- 086
- 087
- 088
- 089
- 090
- 091
- 092
- 093
- 094
- 095
- 096
- 097
- 098
- 099
- 100
void getway(stack <int> &s, const vector <int> &p, int v) {
while(v != -1)
{
s.push(v);
v = p[v];
}
} void compose(int ** M1, int ** M2, int n, int **res) {
int curs;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
curs = 0;
for(int k = 0; k < n; ++k)
{
curs += M1[i][k] * M2[k][j];
}
res[i][j] = curs;
}
}
} int mindist(int from, int to) {
if(from == to)
return 0;
int **res, **tmp;
createMat(res, n);
createMat(tmp, n);
duplit(res, Matrix, n);
for(int i = 1; i < n; ++i)
{
//show(res, n);
if(res[from][to])
{
deleteMat(res, n);
deleteMat(tmp, n);
return i;
}
compose(res, Matrix, n, tmp);
duplit(res, tmp, n);
}
}
int main()
{
fin.open("input.txt");
stack <int> s1, s2;
int d1, d2, min;
fin >> n;
createMat(Matrix, n);
fillnill(Matrix, n);
getGr(n, n);
fin >> from >> to;
--from;
--to;
min = mindist(from, to);
//cerr << min << endl;
d.resize(n);
p.resize(n);
used.assign(n, false);
breadth();
if(used[to])
{
d1 = d[to];
getway(s1, p, to);
swap(from, to);
used.assign(n, false);
d.assign(n, 0);
p.assign(n, 0);
bfs();
d2 = d[to];
if(d1 > min)
{
d1 = d2 / 0;
}
if(!d2 || d2 >= d1)
{
cout << d1 << endl;
while(!s1.empty())
{
cout << (int(s1.top()) + 1) << " ";
s1.pop();
}
}
else
{
d1 = d2 / 0;
getway(s2, p, to);
cout << d2 << endl;
while(!s2.empty())
{
cout << (int(s2.top()) + 1) << " ";
s2.pop();
}
}
}
else
{
cout << -1 << endl;
}
}