c언어 16958번 텔레포트 (백준)

 

#include <stdio.h>

int main(void)
{
	int INF = 10000000;
	int n, t;
    //input
	scanf("%d %d", &n, &t);
	int d[n][3]; //정보를 받을 배열
	int a[n][n]; //최소거리를 저장할 배열
	for(int i = 0; i<n; i++) {
		int e, b, c;
		scanf("%d %d %d", &e, &b, &c);
		d[i][0] = e;
		d[i][1] = b;
		d[i][2] = c;
	}
	
    //거리 초기화
	for(int i = 0; i<n; i++) {
		for(int j = 0; j<n; j++) a[i][j] = INF;
		a[i][i] = 0;
	}
	
    //거리 초기값 넣기
	for(int i = 0; i<n; i++) {
		for(int j = 0; j<n; j++) {
			if(a[i][j] < INF) continue; 
			int x = d[i][1] - d[j][1];
			int y = d[i][2] - d[j][2];
			if(x<0) x*=-1;
			if(y<0) y*=-1;
			int sum = x+y;
			if(d[i][0] == d[j][0] && d[i][0] == 1 && sum > t) sum = t;
			a[i][j] = a[j][i] = sum;  
		}
	}
	
	//floyd warshall
	for(int k = 0; k<n; k++) {
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				if(a[i][k] + a[k][j] < a[i][j])
				a[i][j] = a[i][k] + a[k][j];
			}
		}
	}
    //output
	int loop = 0;
	scanf("%d", &loop);
	while(loop--) {
		int e, b;
		scanf("%d %d", &e, &b);
		printf("%d\n", a[e-1][b-1]);
	}
}

풀이 : Floyd Warshall

0. 정보를 받을 배열과, 최단거리를 저장할 배열을 만든다.

1. 텔레포트 가능여부와, 도시의 위치 x, y을 입력 받는다.

2. 1에서 입력 받은 걸로 특정 도시에서 다른 도시로 가는 것을 모두 구한다.

2.1) x의 값과 y의 값을 합친 것과, 텔레포트가 가능 할 시, 텔레포트가 걸리는 시간과 비교해서 최솟값을 구한다.

3. floyd warshall

4. 출력

 

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

16958번: 텔레포트