Submission #3821430

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int n, m, r;
int memo[205][205] = {0};
vector<int> ls;

int solve();

int main() {
  cin >> n >> m >> r;
  for(int i = 0; i < r; ++i) {
    int x;
    cin >> x;
    --x;
    ls.push_back(x);
  }
  for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
      if(i != j) memo[i][j] = 200000000;
  for(int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    memo[a][b] = memo[b][a] = c;
  }
  for(int k = 0; k < n; ++k)
    for(int i = 0; i < n; ++i)
      for(int j = 0; j < n; ++j)
        memo[i][j] =
            min(memo[i][j], memo[i][k] + memo[k][j]);
  cout << solve() << endl;
  return 0;
}

int solve() {
  int ans = 2000000000;
  sort(ls.begin(), ls.end());
  do {
    int now = 0;
    for(int i = 0; i < r - 1; ++i)
      now += memo[ls[i]][ls[i + 1]];
    ans = min(now, ans);
  } while(next_permutation(ls.begin(), ls.end()));
  return ans;
}

Submission Info

Judge Result