#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e15 + 7;
const ll MAX_N = 2e5 + 10, MAX_K = 5;
ll spec[MAX_K];
ll dist[MAX_K][MAX_N];
ll ans[MAX_N][1 << (MAX_K - 2)];
ll n, k, m;
vector<pair<ll, ll> > g[MAX_N];
void calculate(ll ind) {
for(ll i = 0; i < MAX_N; i ++) {
dist[ind][i] = mod;
}
dist[ind][spec[ind]] = 0;
priority_queue<pair<ll, ll> > pq;
pq.push({0, spec[ind]});
while(!pq.empty()) {
auto curr = pq.top(); pq.pop();
curr.first *= -1;
if(curr.first != dist[ind][curr.second]) {continue;}
for(auto it : g[curr.second]) {
if(dist[ind][it.first] > curr.first + it.second) {
dist[ind][it.first] = curr.first + it.second;
pq.push({-dist[ind][it.first], it.first});
}
}
}
}
ll getAns(ll start, ll finish) {
for(ll i = 0; i < MAX_N; i ++) {
for(ll j = 0; j < (1 << (MAX_K - 2)); j ++) {
ans[i][j] = mod;
}
}
ans[spec[start]][0] = 0;
priority_queue<pair<ll, pair<ll, ll> > > pq;
pq.push({0, {spec[start], 0}});
while(!pq.empty()) {
auto curr = pq.top(); pq.pop();
curr.first *= -1;
for(auto it : g[curr.second.first]) {
if(ans[it.first][curr.second.second] > curr.first + it.second) {
ans[it.first][curr.second.second] = curr.first + it.second;
pq.push({-ans[it.first][curr.second.second], {it.first, curr.second.second}});
}
}
for(ll i = 0, skip = 0; i < k; i ++) {
if(i == start || i == finish) {skip ++; continue;}
if(ans[curr.second.first][curr.second.second | (1 << (i - skip))] > curr.first + dist[i][curr.second.first]) {
ans[curr.second.first][curr.second.second | (1 << (i - skip))] = curr.first + dist[i][curr.second.first];
pq.push({-ans[curr.second.first][curr.second.second | (1 << (i - skip))], {curr.second.first, curr.second.second | (1 << (i - skip))}});
}
}
}
return ans[spec[finish]][(1 << (k - 2)) - 1];
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> k >> m;
for(ll i = 0; i < k; i ++) {
cin >> spec[i];
}
for(ll i = 0; i < m; i ++) {
ll a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
for(ll i = 0; i < k; i ++) {
calculate(i);
}
ll ret = mod;
for(ll i = 0; i < 2; i ++) {
chkmin(ret, getAns(i, j));
}
cout << ret << endl;
return 0;
}
Compilation message
cities.cpp: In function 'int main()':
cities.cpp:94:31: error: 'j' was not declared in this scope
94 | chkmin(ret, getAns(i, j));
| ^
