#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int, int> pii;
typedef pair<ll,pll> lll;
#define fi first
#define se second
void maxi (int &x, int y) {x = max (x, y);}
void mini (int &x, int y) {x = min (x, y);}
const ll maxN = 2e5 + 5, maxLog = 20, mod = 1e9 + 7, inf64 = 1e18, maxK = 5;
class Compare {
public:
bool operator()(lll a, lll b) {
if(a. se. se != b. se. se) return a. se. se > b. se. se;
if(a. fi != b. fi) return a. fi > b. fi;
return a. se. fi > b. se. fi;
}
};
ll n, k, m, a [maxK], dij [maxN] [1 << maxK];
vector <pii> adj [maxN];
priority_queue <lll, vector <lll>, greater <lll>> q;
signed main () {
ios::sync_with_stdio (0);
cin. tie (0);
cout. tie (0);
#define task "untitled1"
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
cin >> n >> k >> m;
for (int i = 0; i < k; i ++) cin >> a [i];
for (int i = 1, u, v, w; i <= m; i ++) {
cin >> u >> v >> w;
adj [u]. push_back ({v, w});
adj [v]. push_back ({u, w});
}
memset (dij, 0x3f, sizeof dij);
for (int i = 0; i < k; i ++) {
dij [a [i]] [1 << i] = 0;
}
for (int fk = 0; fk < (1 << k) - 1; fk ++) {
for (int i = 1; i <= n; i ++) q. push ({dij [i][fk], {i, fk}});
while (!q. empty ()) {
ll dis = q. top (). fi;
pll pos = q. top (). se;
q. pop ();
if (dis != dij [pos. fi] [pos. se]) continue;
for (pll i : adj [pos. fi]) {
if (dij [i. fi] [pos. se] > dij [pos. fi] [pos. se] + i. se) {
dij [i. fi] [pos. se] = dij [pos. fi] [pos. se] + i. se;
q. push ({dij [i. fi] [pos. se], {i. fi, pos. se}});
}
}
}
for (int i = 1; i <= n; i ++) {
for (int msk = 0; msk < (1 << k); msk ++) {
if (fk & msk) continue;
mini (dij [i] [msk | fk], dij [i] [msk] + dij [i] [fk]);
}
}
}
ll ans = inf64;
for (int i = 1; i <= n; i ++) mini (ans, dij [i] [(1 << k) - 1]);
cout << ans;
}
컴파일 시 표준 에러 (stderr) 메시지
cities.cpp: In function 'int main()':
cities.cpp:35:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | freopen (task".inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:36:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen (task".out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |