| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 887314 | vjudge1 | Cities (BOI16_cities) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
#define int long long
#define pb push_back
#define pii array<int, 2>
#define pli pair<ll, int>
const int N = 1e5 + 4;
const ll INF = 4ll * INT_MAX * N;
int n, k, m;
vector<int> imp;
vector<pii> g[N];
ll d[5][N];
bool vis[N];
priority_queue<pli> pq;
void dijkstra(int idx) {
for (int i = 0; i < n; ++i) {
d[idx][i] = INF;
vis[i] = false;
}
pq.push({0, imp[idx]});
d[idx][imp[idx]] = 0;
while (pq.size() > 0) {
int v = pq.top().S;
pq.pop();
if (vis[v] == true) {
continue;
}
vis[v] = true;
for (auto [u, w] : g[v]) {
if (d[idx][v] + w < d[idx][u]) {
d[idx][u] = d[idx][v] + w;
pq.push({d[idx][u], u});
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k >> m;
for (int i = 0; i < k; ++i) {
int v;
cin >> v; --v;
imp.pb(v);
}
for (int i = 0; i < m; ++i) {
int v, u, w;
cin >> v >> u >> w;
--v; --u;
g[v].pb({u, w});
g[u].pb({v, w});
}
for (int i = 0; i < k; ++i) {
dijkstra(i);
}
ll ans = INF;
for (int v = 0; v < n; ++v) {
ll cand = 0;
for (int i = 0; i < k; ++i) {
cand += d[i][v];
}
ans = min(ans, cand);
}
cout << ans;
return 0;
}