c언어 23286번 허들 넘기 (백준)

#include <stdio.h>
#define INF 100000000

int main(void)
{
	int n, m, t; //input
	scanf("%d %d %d", &n, &m, &t);
	int d[n][n]; //최단거리 배열
	for(int i = 0; i<n; i++) { //초기화
		for(int j=0; j<n; j++) {
			d[i][j]=INF;
		}
	}
	
	while(m--) { //간선 정보
		int u, v, h;
		scanf("%d %d %d", &u, &v, &h);
		d[u-1][v-1] = h;
	}
	
	for(int k=0;k<n;k++) //Floyd Warshall
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++) {
		if(d[i][k] < d[i][j] && d[k][j] < d[i][j]) //기존의 것 보다 둘 다 작을 경우
		{   //두 개의 작은 것중 큰 허들
			d[i][j] = (d[i][k] > d[k][j]) ? d[i][k] : d[k][j];
		}
	}
	
	while(t--) { //output
		int s, e;
		scanf("%d %d", &s, &e);
		if(d[s-1][e-1] < INF) printf("%d\n", d[s-1][e-1]);
		else printf("-1\n");
	}
}

 

풀이 : Floyd Warshall

0. n, m, t 입력받기

1. 최단거리 정보를 담는 배열을 초기화

2. 간선정보를 입력받기

3. Floyd Warshall

3-1) 기존의 것 보다 다른 두 개의 것이 둘 다 작다 -> 작은 두 개중 큰 것을 기존의 것에 넣는다.

4. s, e 입력 받은 후, 출력

 

ex) 3-1 자세히

1->2 : 12cm

1->3 : 4cm

3->2 : 8cm

1->2 와 1->3->2에서

12 > 4, 12 > 8이며, 4, 8중 더 큰 것은 8이다.

고로 1->2는 8로 바뀐다. 이를 Floyd Warshall에서 돌리면 된다.

 

https://www.acmicpc.net/problem/23286

23286번: 허들 넘기