Сетевой судья PS [Floyd_Warshal, C++]

Question

Я решаю эту проблему https://www.acmicpc.net/problem/1238

Вы можете изменить язык, нажав кнопку

Идея, которую я придумал, состоит в том, чтобы найти сумму кратчайшего расстояния от Kth до второго и второго до Kth.

так вот весь мой исходный код

#include <stdio.h>
#define INF 999999
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

int ans = 0;
int n,m,x;
int d[1001][1001];

void Floyd_Warshal(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j) d[i][j]=0;
        }
    }
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

void solve(){
    for(int i=1; i<=n; i++){
        if(i==2) continue;
        if(d[i][2] + d[2][i]>ans) ans = d[i][2] + d[2][i];
        //printf("%d = %d+%d \n",ans,d[i][2],d[2][i]);
    }
}

int main(){
    scanf("%d %d %d",&n,&m,&x);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) d[i][j] = INF;
    }
    for(int i=0; i<m; i++){
        int u,v,t;
        scanf("%d %d %d",&u,&v,&t);
        d[u][v] = t;
    }   
    Floyd_Warshal();
    solve();
    printf("%d\n",ans);
    return 0;
}

Я думаю, что функция Floyd_warshal() в порядке.

Но, я думаю, я выбрал неправильный подход (идея, предложенная выше), чтобы решить проблему, поэтому я просто хочу спросить, является ли моя идея правильным подходом к решению проблемы или нет.

Answer 1

Сложность алгоритма Флойда-Варшалла составляет O (n³). Это будет TL.

Решением этой задачи является выполнение SSSP (кратчайший путь из одного источника). Это может эффективно сделать с алгоритмом Дейкстры. Вы можете выполнить Алгоритм Дейкстры на ферме X, а затем повторить его с перевернутыми ребрами. Он имеет сложность O(m logn), если вы пишете его с приоритетными очередями или устанавливаете. Гугл для этого есть много информации, например 1, 2.

После этого ваша идея верна, вы должны взять максимум суммы D[i][X] + D[i][X] для каждой фермы i, Хотя вы написали 2 вместо x, но это, вероятно, опечатка, или для тестирования кода.