백준 14938 (C++) 서강그라운드

문제 이해

평범한 플로이드 와샬 문제다.

map[i][j] = min(map[i][j], map[i][k] + map[k][j]); 

정말 평범한 플로이드 와샬 문제를 풀고싶다면: https://www.acmicpc.net/problem/11404

11404번: 플로이드

 

 

여기서 아이템의 개수를 저장할 배열을 추가로 만든다.

그리고 예은이가 갈 수 있는 범위 안에서 아이템의 개수를 전부 더해주고, max함수로 매번 갱신하면 된다.

 

다시 말해서,

 

예은이가 도달할 지역 n개를 전부 체크한다.

1번 지역에 도착했다면, 1번 지역의 아이템 개수를 더하고, 1번 지역에서 갈 수 있는 범위에 있는 아이템을 전부 더한다.

2번 지역에서도 동일하게 진행한다

3번 지역에서도 

.

.

.

n개 지역에서 체크한 아이템의 합 중 최대값이 문제의 답이 될 것이다.

 

 

 

 

 

 

 

 

---

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int INF = 1e8;
const int MAX = 100;
int n, m, r, sum=0, ans=0;
int map[MAX][MAX];
int item[MAX];
void fw() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        sum += item[i];
        for (int j = 1; j <= n; j++) {
            if (i != j && map[i][j] <= m) {
                sum += item[j];
            }
        }
        ans =max(ans, sum);
        sum = 0;
    }
    cout << ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> r;
    for (int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        item[i] = t;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            map[i][j] = INF;
            if (i == j) map[i][j] = 0;
        }
    }
    for (int i = 1; i <= r; i++) {
        int a, b, l;
        cin >> a >> b >> l;
        map[a][b] = map[b][a] = l;
    }
    fw();
    return 0;
}

 

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

14938번: 서강그라운드

 

얏호~ 내 이름 검색해서 나오길래 풀었다.