c언어 14938번 서강그라운드 (백준)

#include <stdio.h>
#define INF 100000000

int main(void)
{
	int n, m, r; //입력
	scanf("%d %d %d", &n, &m, &r);
	int d[n][n]; //최단 거리를 담는 배열
	int bag[n]; //각 구역에서 얻는 물건들 개수
	
	for(int i=0; i<n; i++) { //최단거리 배열 초기화
		for(int j=0; j<n; j++) d[i][j]=INF;
		d[i][i]=0; //자기 자신의 거리는 0
	}
	
	for(int i=0; i<n; i++) scanf("%d", &bag[i]); //각 구역에서 얻을 수 있는 물건의 개수 입력
	
	while(r--) { //간선 정보 입력 (양방향)
		int a, b, l;
		scanf("%d %d %d", &a, &b, &l); 
		d[b-1][a-1] = d[a-1][b-1] = l; //양방향
	}
	
	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[k][j] < d[i][j]) 
		d[i][j] = d[i][k] + d[k][j];
	}
	
	int max = 0; //최댓값을 담는 변수
	for(int i=0; i<n; i++) { //최댓값 구하기
		int cnt = 0;
		for(int j=0; j<n; j++) {
			if(d[i][j] <= m) cnt += bag[j];
		} if(max < cnt) max = cnt;
	} printf("%d", max); //최댓값 출력
}

풀이 : Floyd Warshall

0. n, m , r 입력받음

1. 최단 거리 배열 초기화

2. 각 구역의 물건 개수를 입력받기

3. 간선의 정보 입력받기 (양방향!!!!)

4. Floyd Warshall

5. 최댓값 구하기

6. 최댓값 출력

 

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

14938번: 서강그라운드