c - 在线法官 PS [Floyd_Warshal, C++]

Question

我正在解决这个问题 https://www.acmicpc.net/problem/1238#

您可以通过单击按钮更改语言

我想到的想法是求第K个到第二个和第二个到第K个的最短距离之和

这是我的整个源代码

#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

Floyd-Warshall 算法的复杂度为O(n³)。这将是 TL。

此任务的解决方案是执行SSSP(单源最短路径)。它可以有效地配合 Dijkstra 算法。您可以在农场 X 上执行 Dijkstra 算法，然后在边缘反转的情况下再次执行该算法。如果您使用优先级队列或集合编写它，则其复杂度为O(m logn)。 Google一下这个，有很多资料，例如1 , 2 .

在此之后，您的想法是正确的，您应该为每个农场i取最大总和D[i][X] + D[i][X]。虽然你写的是 2 而不是 x，但这可能是一个拼写错误，或者是为了测试代码。