| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1040996 | mdn2002 | Board Game (JOI24_boardgame) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
Mayoeba Yabureru
*/
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, m, k;
string s;
cin >> n >> m >> k;
vector gr(n + 1,vector<int>());
vector<int> X(n + 1), type(n + 1);
vector con(n + 1, vector<long long>(k + 1, 1e9));
con[0].assign(k + 1, 0);
for (int i = 1; i <= m; i ++) {
int x, y;
cin >> x >> y;
gr[x].push_back(y);
gr[y].push_back(x);
}
cin >> s;
s.insert(s.begin(), '*');
for (int i = 1; i <= k; i ++) cin >> X[i];
for (int i = 1; i <= n; i ++) {
if (s[i] == '0') continue;
type[i] = 1;
for (auto j : gr[i]) {
if (s[j] == '1') type[i] = 2;
}
}
for (int i = 2; i <= k; i ++) {
vector<long long> dis(n + 1, 1e9);
queue<pair<int, int>> q;
vector<pair<int, long long>> nq;
dis[X[i]] = 0;
q.push({X[i], 0});
int t = 0;
while (t + 1 <= n) {
while (q.size()) {
auto [x, type] = q.front();
q.pop();
for (auto u : gr[x]) {
if (dis[u] > dis[x] + 1) {
dis[u] = dis[x] + 1;
if (s[u] == '0') q.push({u, 1});
else {
con[t + 1][i] = min(con[t + 1][i], dis[u]);
nq.push_back({u, dis[u]});
}
}
}
if (type == 0) dis[x] = 1e9;
}
if (nq.size() == 0) break;
dis.assign(n + 1, 1e9);
for (auto [x, y] : nq) {
q.push({x, 0});
dis[x] = min(dis[x], y);
}
nq.clear();
t ++;
}
}
vector<long long> dis(n + 1, 1e18), ans(n + 1, 1e18);
queue<int> q, nq;
dis[X[1]] = 0;
q.push(X[1]);
int t = 0;
while (true) {
long long add = 0;
for (int i = 2; i <= k; i ++) add += con[t][i];
while (q.size()) {
int x = q.front();
ans[x] = min(ans[x], dis[x] + add);
q.pop();
for (auto u : gr[x]) {
if (dis[u] > dis[x] + 1) {
dis[u] = dis[x] + 1;
if (s[u] == '0') q.push(u);
else {
ans[u] = min(ans[u], dis[u] + add);
nq.push(u);
}
}
}
}
if (nq.size() == 0) break;
q = nq;
while (nq.size()) nq.pop();
t ++;
}
for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
}
/*
5 5 2
1 2
2 3
2 4
3 5
4 5
01000
1 5
12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11
*/
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
for (int I = 0; I < T; I ++){
solve();
}
}