Реализация решения задачи. Помогите, пожалуйста!

Question

Реализация решения задачи. Помогите, пожалуйста!

Марк Семенов Ученик (105), на голосовании 1 неделю назад

У меня есть такая задача: https://informatics.msk.ru/mod/statements/view.php?chapterid=2598#1
И у меня есть такая идея решения:
Напишем Флойда-Уоршелла и посчитаем максимальное
расстояние между каждой парой вершин. Флойд на максимум это Флойд на минимум, только вместо min() max().
После этого, если у нас нет положительных циклов, то всё ищется легко. Мы бежим по нашему максимальному маршруту и выводим его вершины.
Как проверить наличие положительного цикла? Если у нас в матрице дистанций алгоритма Флойда-Уоршлелла d[i][i] > 0, то либо из i достижим положительный цикл, либо она сама лежит на положительном цикле. Это как минимум означает, что у нас есть положительный цикл.
То есть, алгоритм решения:
1) Насчитываем расстояния алгоритмом Флойда-Уоршелла "наоборот"
2) Для каждой ai в которой давать концерт мы смотрим, не достижим ли из неё положительный цикл.
3) Если достижим, то выводим infinitely kind. Если нет, то просто выводим маршрут, который построили.

Только вот я не могу придумать как простым образом этот маршрут перелётов трекать. Можете помочь с кодом?

Вот мой набросок:

 #pragma GCC optimize("unroll-loops") 
#pragma GCC optimize("O3") 
#pragma GCC target("avx2") 
 
#include  
 
using namespace std; 
 
const int INF = 1e9; 
 
void restore_path(int s, int t, vector>& parent) { 
    vector path; 
    for (int v = t; v != s; v = parent[s][v]) { 
        path.push_back(v); 
    } 
    path.push_back(s); 
    reverse(path.begin(), path.end()); 
    for (int i = 0; i < path.size(); ++i) { 
        cout << (path[i] + 1) << " ";  
    } 
    cout << '\n'; 
} 
 
signed main(){ 
     
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
     
    int n, m, k; cin >> n >> m >> k; 
    vector> d(n, vector(n, INF));  
    vector concerts; 
    vector> parent(n, vector(n)); 
    for(int i = 0; i < m; i++){ 
        int b, e, w; cin >> b >> e >> w; 
        --b; --e; 
        d[b][e] = w; 
    } 
    for(int i = 0; i < k; i++){ 
        int l; cin >> l; 
        concerts.push_back(l); 
    } 
     
    for(int k = 0; k < n; k++) 
        for(int i = 0 ; i < n; i++) 
            for(int j = 0; j < n; j++) 
                if(d[i][k] < INF && d[k][j] < INF){ 
                    d[i][j] = max(d[i][j], d[i][k] + d[k][j]); 
                    parent[i][j] = parent[k][j]; 
                } 
     
    for(int i = 0; i < k; i++){ 
        if(d[concerts[i]][concerts[i]] > 0){ 
            cout << "infinitely kind" << '\n'; 
            return 0; 
        } 
    } 
     
    // вот сюда нужно добавить код. 
     
    return 0; 
}

Answer 1

 #include  
 
using namespace std; 
 
const int INF = 1e9; 
 
void restore_path(int s, int t, vector>& parent) { 
    vector path; 
    for (int v = t; v != s; v = parent[s][v]) { 
        path.push_back(v); 
    } 
    path.push_back(s); 
    reverse(path.begin(), path.end()); 
    for (int i = 0; i < path.size(); ++i) { 
        cout << (path[i] + 1) << " "; 
    } 
    cout << '\n'; 
} 
 
signed main(){ 
 
    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
 
    int n, m, k; 
    cin >> n >> m >> k; 
    vector> d(n, vector(n, INF)); 
    vector concerts; 
    vector> parent(n, vector(n)); // Добавляем матрицу родительских вершин 
 
    for(int i = 0; i < m; i++){ 
        int b, e, w; 
        cin >> b >> e >> w; 
        --b; --e; 
        d[b][e] = w; 
        parent[b][e] = b; // Устанавливаем начальную вершину для каждой дуги 
    } 
 
    for(int i = 0; i < k; i++){ 
        int l; 
        cin >> l; 
        concerts.push_back(l); 
    } 
 
    for(int k = 0; k < n; k++) 
        for(int i = 0 ; i < n; i++) 
            for(int j = 0; j < n; j++) 
                if(d[i][k] < INF && d[k][j] < INF){ 
                    d[i][j] = max(d[i][j], d[i][k] + d[k][j]); 
                    if(d[i][j] == d[i][k] + d[k][j]) // Если нашли более длинный путь через k 
                        parent[i][j] = parent[k][j]; // Записываем, что вершина j достигается из k 
                } 
 
    for(int i = 0; i < k; i++){ 
        if(d[concerts[i]][concerts[i]] > 0){ 
            cout << "infinitely kind" << '\n'; 
            return 0; 
        } 
    } 
 
    // Выводим маршруты 
    for (int i = 0; i < k - 1; ++i) { 
        restore_path(concerts[i], concerts[i + 1], parent); 
    } 
 
    return 0; 
}

Теперь parent[i][j] хранит информацию о том, из какой вершины i был достигнут город j. Таким образом, после выполнения алгоритма Флойда-Уоршелла у вас будет полная информация о маршруте от каждого города до каждого другого.