문제

문제 링크

입력

첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.

둘째 줄에는 n개의 숫자가 차례대로 각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.

세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.

출력

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

예제

입력
5 5 4
5 7 8 2 3
1 4 5
5 2 4
3 2 3
1 2 3

출력
23

나의 접근 방법

모든 정점에서 모든 정점으로의 최단 거리를 구해야 하는 문제이다. 플로이드-와샬 알고리즘으로도 풀 수 있을 것 같은데 다익스트라가 익숙해서 다익스트라로 풀었다.
각 정점에서 다익스트라를 한 번씩 돌린 후 최단 거리가 m보다 작은 정점들의 아이템 수를 더해주면 된다.

코드

#include<iostream>
#include<queue>
#include<vector>
#include<functional>
#include<algorithm>
using namespace std;

#define MAX 1000000000

typedef pair<int, int> pii;

int main(void){
  int n, m, r, result = 0;
  vector<int> value(101);
  vector<vector<int>> inputs(101, vector<int>(101)), dist(101, vector<int>(101, MAX));
  cin>>n>>m>>r;
  for(int i = 1 ; i<=n ; i++){
    cin>>value[i];
  }
  for(int i = 0 ; i<r ; i++){
    int a, b, l;
    cin>>a>>b>>l;
    inputs[a][b] = l;
    inputs[b][a] = l;
  }
  for(int i = 1 ; i<=n ; i++){
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.push({0, i});
    dist[i][i] = 0;
    while(!pq.empty()){
      pii now = pq.top();
      int nowValue = now.first, nowIdx = now.second;
      pq.pop();
      for(int j = 1 ; j<=n ; j++){
        if(!inputs[nowIdx][j]) continue;
        int nextValue = nowValue + inputs[nowIdx][j];
        if(dist[i][j] > nextValue){
          dist[i][j] = nextValue;
          pq.push({nextValue, j});
        }
      }
    }
  }
  for(int i = 1 ; i<=n ; i++){
    int sum = 0;
    for(int j = 1 ; j<=n ; j++){
      if(dist[i][j] <= m) sum += value[j];
    }
    result = max(result, sum);
  }
  cout<<result;
  return 0;
}