| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1270163 | MateiKing80 | Board Game (JOI24_boardgame) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
const int inf = 1e18;
const int BULAN = 100;
using pii = pair<int, int>;
#define fr first
#define sc second
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> vec(n);
vector<bool> stop(n);
for (int i = 0; i < m; i ++) {
int u, v;
cin >> u >> v;
u --, v --;
vec[u].push_back(v);
vec[v].push_back(u);
}
int nrStop = 0;
for (int i = 0; i < n; i ++) {
char ch;
cin >> ch;
stop[i] = ch - '0';
nrStop += stop[i];
}
if (nrStop <=
vector<int> start(k);
for (int i = 0; i < k; i ++) {
cin >> start[i];
start[i] --;
}
vector<int> distStart(n, inf), dp(n, 0);
distStart[start[0]] = 0;
queue<int> st;
st.push(start[0]);
vector<bool> viz(n, false);
while (!st.empty()) {
int x = st.front();
st.pop();
if ((x != start[0] && stop[x]) || viz[x])
continue;
viz[x] = true;
for (auto i : vec[x]) {
distStart[i] = min(distStart[i], 1 + distStart[x]);
st.push(i);
}
}
vector<int> ans(n, inf);
vector<bool> doubleStop(n, false);
for (int i = 0; i < n; i ++) {
for (auto j : vec[i])
if (stop[i] && stop[j])
doubleStop[i] = true;
}
vector<int> init(n, inf);
for (int i = 0; i < n; i ++)
if (stop[i]) {
st.push(i);
init[i] = 0;
}
viz.assign(n, 0);
while (!st.empty()) {
int x = st.front();
st.pop();
if (viz[x])
continue;
viz[x] = true;
for (auto i : vec[x]) {
init[i] = min(init[i], init[x] + 1);
st.push(i);
}
}
for (auto &i : init)
if (i == 0)
i += 2;
for (int i = 0; i < n; i ++)
if (doubleStop[i])
init[i] --;
deque<int> dq;
vector<int> init2(n, inf);
for (int i = 0; i < n; i ++)
if (doubleStop[i]) {
init2[i] = 0;
dq.push_back(i);
}
viz.assign(n, 0);
while (!dq.empty()) {
int x = dq.front();
dq.pop_front();
if (viz[x])
continue;
viz[x] = true;
for (auto i : vec[x]) {
int cost = (stop[x] == 0);
init2[i] = min(init2[i], init2[x] + cost);
if (cost)
dq.push_back(i);
else
dq.push_front(i);
}
}
vector<int> schimb;
for (int i = 1; i < k; i ++)
schimb.push_back(init2[start[i]] - init[start[i]] + 2);
int add = 2 * (k - 1), point = 0;
sort(schimb.begin(), schimb.end());
int sum = 0;
vector<int> cost(n + 1);
for (int rep = 0; rep <= n; rep ++) {
if (rep == 1)
for (int i = 1; i < k; i ++)
sum += init[start[i]];
if (rep > 1)
sum += add;
if (rep >= 1) {
while (point < (int)schimb.size() && schimb[point] <= rep) {
add --;
point ++;
}
}
cost[rep] = sum;
}
for (int i = 0; i < n; i ++)
ans[i] = min(ans[i], distStart[i]);
if (k <= BULAN || nrStop <= 1) {
for (int cst = k; cst <= 2 * k - 1; cst ++) {
priority_queue<pair<int, int>> pq;
pq.push({0, start[0]});
vector<pair<int, int>> dist(n, {inf, 0});
dist[start[0]] = {0, 0};
viz.assign(n, 0);
while (!pq.empty()) {
int x = pq.top().second;
pq.pop();
if (viz[x])
continue;
viz[x] = true;
for (auto i : vec[x]) {
if (stop[x] && x != start[0]) {
dist[i] = min(dist[i], {dist[x].first + cst, dist[x].second + 1});
} else {
dist[i] = min(dist[i], {dist[x].first + 1, dist[x].second});
}
pq.push({-dist[i].first, i});
}
}
for (int i = 0; i < n; i ++)
ans[i] = min(ans[i], cost[dist[i].second] + dist[i].first - (cst - 1) * dist[i].second);
}
} else {
dq.clear();
dq.push_back(start[0]);
vector<int> dist(n, inf);
dist[start[0]] = 0;
viz.assign(n, 0);
while (!dq.empty()) {
int x = dq.front();
dq.pop_front();
if (viz[x])
continue;
viz[x] = true;
for (auto i : vec[x]) {
if (stop[x] && x != start[0]) {
dist[i] = min(dist[i], dist[x] + 1);
dq.push_back(i);
} else {
dist[i] = min(dist[i], dist[x]);
dq.push_front(i);
}
}
}
int upper = n / (k - 1) + 5;
queue<pair<int, int>> q;
q.push({start[0], 0});
vector<vector<int>> dst(n, vector<int> (upper, inf));
dst[start[0]][0] = 0;
vector<vector<bool>> vz(n, vector<bool> (upper, false));
while (!q.empty()) {
int nod = q.front().first;
int nrx = q.front().second;
q.pop();
if (vz[nod][nrx - dist[nod]])
continue;
vz[nod][nrx - dist[nod]] = true;
for (auto i : vec[nod]) {
if (stop[nod] && nod != start[0]) {
if (nrx + 1 < dist[i] + upper) {
dst[i][nrx + 1 - dist[i]] = min(dst[i][nrx + 1 - dist[i]], dst[nod][nrx - dist[nod]] + 1);
q.push({i, nrx + 1});
}
} else {
if (nrx < dist[i] + upper) {
dst[i][nrx - dist[i]] = min(dst[i][nrx - dist[i]], dst[nod][nrx - dist[nod]] + 1);
q.push({i, nrx});
}
}
}
}
for (int i = 0; i < n; i ++)
for (int j = 0; j < upper; j ++)
if (j + dist[i] <= n)
ans[i] = min(ans[i], cost[j + dist[i]] + dst[i][j]);
}
for (int i = 0; i < n; i ++)
cout << ans[i] << '\n';
}