|
|
back to boardaccepted Posted by Mikhail 13 May 2018 18:24 //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; const int maxn = 100; int c[maxn][maxn]; bool good[maxn]; int n; bool f (ii a, ii b) { if (c[a.fi][a.se] != c[b.fi][b.se]) re c[a.fi][a.se] < c[b.fi][b.se]; re a < b; } bool check () { fo(i, n) if (!good[i]) re false; re true; } set <ii, bool (*)(ii, ii)> s(f); int main() { int k; cin >> n >> k; fo(i, k) { int x; cin >> x; good[x - 1] = true; } fo(i, n) fo(j, n) cin >> c[i][j]; fo(j, n) fo(i, n) if (i != j && good[j] && !good[i]) s.insert(mp(j, i)); int ans = 0; while (!check()) { ii best = *s.begin(); fo(i, n) s.erase(mp(i, best.se)); ans += c[best.fi][best.se]; good[best.se] = true; fo(i, n) if (i != best.se && !good[i]) s.insert(mp(best.se, i)); } cout << ans << endl; } |
|
|