Baekjoon 14938번 서강그라운드

문제

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

걸린 시간

풀이

00 : 11 : 59

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, r;
    cin >> n >> m >> r;
    vector<int> item(n);
    for(auto& i : item) cin >> i;
    vector<vector<int>> adj(n, vector<int>(n, INF));
    for(int i = 0; i < n; i++)
        adj[i][i] = 0;
    int a, b, l;
    for(int i = 0; i < r; i++){
        cin >> a >> b >> l;
        adj[a-1][b-1] = l;
        adj[b-1][a-1] = l;
    }
    for(int k = 0; k < n; k++)
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
    int ans = 0;
    for(int i = 0; i < n; i++){
        int tmp = 0;
        for(int j = 0; j < n; j++)
            if(adj[i][j] <= m) tmp += item[j];
        ans = max(ans, tmp);
    }
    cout << ans;
    return 0;
}

각각의 지역에서 다른 지역까지의 거리(수색 범위)는 플로이드-와샬 알고리즘으로 한번에 구할 수 있다.