플로이드 워셜

전처리

int INF = 100000000;

int[][] dist = new int[V+1][V+1];

for (int i=0; i<E; i++)
{
    st = new StringTokenizer(input.readLine());

    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    int w = Integer.parseInt(st.nextToken());

    dist[u][v] = w;
}

 

순서 k i j 순

이거 다르게하면 답 틀림

 

 

static int[][] Floyd_Warshall (int[][] dist, int N, int INF)
{
    int[][] G = new int[N+1][N+1];

    for (int i=1; i<=N; i++)
    {
        for (int j=1; j<=N; j++)
        {
            if ( i !=j && dist[i][j] == 0 )
                G[i][j] = INF;
            else
                G[i][j] = dist[i][j];
        }
    }

    for (int k=1; k<=N; k++)
        for (int i=1; i<=N; i++)
            for (int j=1; j<=N; j++)
                G[i][j] = Math.min(G[i][j], G[i][k] + G[k][j]);

    return G;
}