- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 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;
}
}
еще умиляет одновременное использование std::vector<int> и int **
>d1 = d2 / 0;
А это зачем?
Исключения слишком мейнстрим.