oj.uz

답안 #641962

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
641962 2022-09-18T03:55:41 Z andecaandeci Cities (BOI16_cities) C++17
0 / 100
 6000 ms 26584 KB 
#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 N(k);
  vector <vector <pii>> E(n + 1);
  map <int, int> M;
  for(int i = 0; i < k; i++) cin >> N[i];
  for(int i = 0; i < m; i++){
    int a, b, c; cin >> a >> b >> c;
    E[a].pb({b, c});
    E[b].pb({a, c});
  }
  for(int i = 0; i < k; i++) M[N[i]]++;
  int ans = LLONG_MAX;
  for(int i = 1; i <= n; i++){
    vi V(n + 1, 0);
    priority_queue <pii, vector <pii>, greater <pii>> Q;
    Q.push({0, i});
    int sum = 0;
    // cout << "A;" << endl;
    while(Q.size()){
      int val = Q.top().fi, cur = Q.top().se;
      Q.pop();
      // cout << cur << " " << val << endl; 
      if(V[cur]) continue;
      V[cur] = 1;
      if(M[cur]){
        sum += val;
        val = 0;
      }

      for(auto it : E[cur]){
        Q.push({val + it.se, it.fi});
      }
    }
    // cout << endl;
    // cout << i << " " << sum << endl;
    ans = min(ans, sum);
  }
  cout << ans << "\n";

}

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6046 ms 26584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 471 ms 560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6049 ms 26468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 6088 ms 26476 KB Time limit exceeded
2 Halted 0 ms 0 KB -