제출 #641959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641959		makanhulia	Cities (BOI16_cities)	C++17	0 / 100	6089 ms	24904 KiB

cities

#include <bits/stdc++.h>

#define mp make_pair
#define int long long
#define pb push_back
#define STC stack <int>
#define pii pair <int, int>
#define vi vector <int>
#define vii vector <vi >
#define se second
#define fi first

using namespace std;
const int mod = 1e9 + 7;
const int MxN = 1e9 + 7;

signed main(){

  ios_base::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(NULL);

  int n, k, m; cin >> n >> k >> m;
  vi P(k);
  vector <vector <pii>> N(n + 1);
  for(int i = 0; i < k; i++) cin >> P[i];
  for(int i = 0; i < m; i++){
    int a, b, c; cin >> a >> b >> c;
    N[a].pb({b, c});
    N[b].pb({a, c});
  }  

  int ans = LLONG_MAX;
  for(int i = 1; i <= n; i++){
    priority_queue <pii, vector <pii>, greater <pii>> Q;
    Q.push({0, i});
    vi V(n+1, 1e18);

    while(Q.size()){
      int val = Q.top().fi, cur = Q.top().se;
      Q.pop();

      if(V[cur] < val) continue;
      V[cur] = val;

      for(auto it : N[cur]){
        Q.push({val + it.se, it.fi});
      }
    }

    int sum = 0;
    for(int j = 0; j < k; j++) sum += V[P[j]];
    ans = min(ans, sum);
  }
  cout << ans << "\n";
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26