라이브러리/JAVA
플로이드 워셜
kimximya
2024. 7. 3. 05:18
전처리
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;
}