BOJ 14938: 서강그라운드

#BOJ 14938: 서강그라운드

14938번: 서강그라운드

#풀이

문제를 읽어보면 배틀그라운드를 말하는 것 같다... ㅋㅋㅋㅋ

 

 

일단 수색경로 안에 있는 지역을 가서 가장 많은 아이템을 먹어야 한다.

 

플로이드를 사용하여 해결할 수 있다.

 

먼저 인접행렬을 통해 i->j까지의 최단경로의 비용을 알 수 있다.

 

수색반경 이내에 들어 있는 마을가기 위해 nxt 배열을 통해 경로를 알아야 한다.

 

또한 방문표시 배열을 사용하여 내가 거쳐간 마을을 확인 후 아이템을 더한다.

 

방문표시를 사용하는 이유가 i->j할 때 i->k->j이렇게 거쳐가는 마을도 있을 텐데 k가 중복해서 방문하기 때문에 아이템을 여러 번 더할 수 있어 방문표시를 하는 것이 좋다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
int n, m, r;
int adj[101][101];
int nxt[101][101];
int vis[101];
int item[101];
int INF = 0x3f3f3f3f;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n>>m >>r;
	for(int i = 1; i <= n; i++) 
		fill(adj[i] + 1, adj[i]+n+1, INF);
	for(int i =1 ;i<=n; i++){
		cin >> item[i];
	}
	
	for(int i = 0; i < r; i++){
		int w, a, b;
		cin >> a >> b >> w;
		adj[a][b] = w;
		adj[b][a] = w;
		nxt[a][b] = b;
		nxt[b][a] = a;
	}
	
	for(int i =1; i <=n; i++){
		adj[i][i] = 0;
	}
	
	for(int k = 1; k <=n; k++){
		for(int i = 1; i <=n; i++){
			for(int j = 1; j <=n; j++){
				if(adj[i][j] > adj[i][k] + adj[k][j])
				{
					adj[i][j] = adj[i][k] + adj[k][j];
					nxt[i][j] = nxt[i][k];
				}
			}
		}
	}
	
	int ans = 0, item_count;
	for(int i = 1; i <= n; i++){
	    item_count = 0;
	    fill(vis + 1, vis + n + 1, 0);

	    for(int j = 1; j <= n; j++) {
	      if(adj[i][j] > m) continue;
		
		int cur = i;
		while(cur != j)
		{
			vis[cur] = 1;
			cur = nxt[cur][j];
		
		}
		vis[j] = 1;
	    }
	    for(int z = 1; z <=n; z++){
	    	if(vis[z]) item_count += item[z];
	    }
	    ans = max(ans, item_count);
	  } 
	  cout << ans << '\n';
	return 0;
}