/*
Sag Template by ParsaF(RBS Master)
*/
// Heaven
#include <bits/stdc++.h>
/*
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
*/
using namespace std;
#define TOF_IO ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define File_IO(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
#define SEP ' '
#define endl '\n'
#define F first
#define S second
#define ALL(x) (x).begin(), (x).end()
#define sz(x) (x).size()
#define PB push_back
#define toLower(x) transform(ALL(x), x.begin(), ::tolower)
#define toUpper(x) transform(ALL(x), x.begin(), ::toupper)
#define EDGE(arr, x, y) arr[x].PB(y), arr[y].PB(x)
#define WEDGE(arr, x, y, z) arr[x].PB({y, z}), arr[y].PB({x, z})
#define debug(x) cerr << #x << ": " << x << endl
#define kill(x) cout << x << endl, exit(0);
#define BIPC(x) __builtin_popcount(x);
#define fD1(arr, ind, x) for(int i=0; i<ind; i++) arr[i] = x;
#define fD2(arr, ind1, ind2, x) for(int i=0; i<ind1; i++) for(int j=0; j<ind2; j++) arr[i][j] = x;
#define lc (id << 1)
#define rc ((id << 1) | 1)
#define isLeaf r - l == 1
typedef long long ll;
typedef long double lld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e5 + 20;
const ll MAXN = 10 + 5;
const ll MT = 323 + 0;
const ll sq = 320;
const ll M = 1e8 + 0;
const ll IM = 1e18 + 37;
const ll LOG = 6;
const ll INF = 1e18;
const lld EPS = 0.00000001;
ll prime[] = {1000000009, 1000000007, 988244353, 1000696969, 696969569, 1223232323};
/*********************************************************** Dark side of Heaven ************************************************************/
/***************************************************************************************************************************************************/
ll POW(ll a, ll b, ll md);
ll LIS(vector<ll>& v);
ll MOD(ll a, ll b);
void printYES(bool flag);
void printYes(bool flag);
inline ll mod_add(ll a, ll b);
inline ll mod_neg(ll a, ll b);
inline ll mod_mlt(ll a, ll b);
/*
ll factI[N + 1], Numi[N + 1], fact[N + 1];
void InverseofNumber(ll p); void InverseofFactorial(ll p); void factorial(ll p); ll nPr(ll N, ll R, ll p); ll nCr(ll N, ll R); void comb();
*/
ll n, k, m;
ll C[6];
vector<pll> G1[N];
ll dp[(1<<LOG)][N];
void solve()
{
cin >> n >> k >> m;
for(int i=0; i<k; i++) cin >> C[i], C[i]--;
for(int i=0; i<m; i++)
{
ll v, u, w;
cin >> v >> u >> w; v--; u--;
WEDGE(G1, v, u, w);
}
for(int mask=0; mask<(1<<k); mask++) for(int i=0; i<n; i++) dp[mask][i] = INF;
for(int i=0; i<k; i++) dp[(1<<i)][C[i]] = 0;
for(int mask=1; mask<(1<<k); mask++)
{
for(int i=0; i<k; i++) if((mask>>i)&1) for(int v=0; v<n; v++) dp[mask][v] = min(dp[mask][v], dp[mask^(1<<i)][v] + dp[(1<<i)][v]);
set<pll> st;
for(int i=0; i<n; i++) if(dp[mask][i] < INF) st.insert({dp[mask][i], i});
while(sz(st))
{
auto itr = st.begin();
ll v, d;
v = itr -> S; d = itr -> F;
st.erase(itr);
if(dp[mask][v] != d) continue;
for(auto P: G1[v])
{
ll u, w;
u = P.F; w = P.S;
if(w+d >= dp[mask][u]) continue;
dp[mask][u] = w+d;
st.insert({dp[mask][u], u});
}
}
}
ll ans = INF;
ll f = (1<<k)-1;
for(int i=0; i<n; i++) ans = min(ans, dp[f][i]);
cout << ans << endl;
}
int main()
{
//TOF_IO;
ll nTest=1;
//cin >> nTest;
while(nTest--) solve();
return 0;
}
/******************************************************** The line that separates heaven and hell *******************************************************/
// HELL
/*
void InverseofNumber(ll p = M){Numi[0] = Numi[1] = 1; for (ll i = 2; i <= N; i++){Numi[i] = Numi[p % i] * (p - p / i) % p;}}
void InverseofFactorial(ll p = M){factI[0] = factI[1] = 1;for (ll i = 2; i <= N; i++){factI[i] = (Numi[i] * factI[i - 1]) % p;}}
void factorial(ll p = M){fact[0] = 1;for (ll i = 1; i <= N; i++){fact[i] = (fact[i - 1] * i) % p;}}
ll nPr(ll N, ll R, ll p = M){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N]) % p * factI[N - R]) % p;return ans;}
ll nCr(ll N, ll R){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N] * factI[R]) % M * factI[N - R]) % M;return ans;}
void comb(){ll p = M;InverseofNumber(p);InverseofFactorial(p);factorial(p);}
*/
ll POW(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? MOD(a * POW(MOD(a * a, md), b / 2, md), md) : MOD(POW(MOD(a * a, md), b / 2, md), md)));}
ll MOD(ll a, ll b){return (a%b + b) % b;}
ll LIS(vector<ll>& v){if (v.size() == 0) {return 0;} vector<ll> tail(v.size(), 0); ll length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
void YES(bool flag){cout << (flag? "YES\n" : "NO\n");}
void Yes(bool flag){cout << (flag? "Yes\n" : "No\n");}
inline ll mod_add(ll a, ll b){ ll res = a + b; return (res >= M? res - M : res); }
inline ll mod_neg(ll a, ll b){ ll res = (abs(a - b) < M? a - b : (a - b) % M); return (res < 0? res + M : res); }
inline ll mod_mlt(ll a, ll b){ return (a * b % M); }
Compilation message
cities.cpp: In function 'll LIS(std::vector<long long int>&)':
cities.cpp:180:133: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | ll LIS(vector<ll>& v){if (v.size() == 0) {return 0;} vector<ll> tail(v.size(), 0); ll length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
7516 KB |
Output is correct |
| 2 |
Correct |
2 ms |
7516 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9564 KB |
Output is correct |
| 4 |
Correct |
2 ms |
15708 KB |
Output is correct |
| 5 |
Correct |
4 ms |
28108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
701 ms |
33360 KB |
Output is correct |
| 2 |
Correct |
729 ms |
33628 KB |
Output is correct |
| 3 |
Correct |
277 ms |
23316 KB |
Output is correct |
| 4 |
Correct |
124 ms |
21692 KB |
Output is correct |
| 5 |
Correct |
356 ms |
30732 KB |
Output is correct |
| 6 |
Correct |
122 ms |
19792 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
16216 KB |
Output is correct |
| 2 |
Correct |
8 ms |
15964 KB |
Output is correct |
| 3 |
Correct |
6 ms |
15708 KB |
Output is correct |
| 4 |
Correct |
7 ms |
15776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1505 ms |
41444 KB |
Output is correct |
| 2 |
Correct |
1520 ms |
41960 KB |
Output is correct |
| 3 |
Correct |
660 ms |
31564 KB |
Output is correct |
| 4 |
Correct |
787 ms |
35708 KB |
Output is correct |
| 5 |
Correct |
239 ms |
29880 KB |
Output is correct |
| 6 |
Correct |
130 ms |
30288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3178 ms |
54076 KB |
Output is correct |
| 2 |
Correct |
3062 ms |
54000 KB |
Output is correct |
| 3 |
Correct |
3058 ms |
54084 KB |
Output is correct |
| 4 |
Correct |
1392 ms |
43876 KB |
Output is correct |
| 5 |
Correct |
1487 ms |
47684 KB |
Output is correct |
| 6 |
Correct |
353 ms |
42736 KB |
Output is correct |
| 7 |
Correct |
141 ms |
42576 KB |
Output is correct |
