| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 28585 | 볼빨간 승관이 (#68) | Alternative Mart (FXCUP2_mart) | C++98 | 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.
#include<bits/stdc++.h>
using std::vector;
using std::pair;
using pii = pair<int, int>;
vector<pii> dist[50010];
vector<pii> G[50010];
bool chk[50010];
struct node {
int d;
int idx;
int from;
bool operator>(const node& p)const {
return d > p.d;
}
};
pii has(const vector<pii>& vec, int a) {
for (auto& b : vec) {
if (b.second == a)return b;
}
return{ -1,-1 };
}
int main() {
int n, m, k, q;
scanf("%d%d%d%d", &n, &m, &k, &q);
std::queue<node> que;
for (int i = 0; i < k; i++) {
int a;
scanf("%d", &a);
que.push({ 0,a,a });
dist[a].push_back({ 0,a });
}
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
G[a].push_back({ b,c });
G[b].push_back({ a,c });
}
while (!que.empty()) {
int idx = que.front().idx;
que.pop();
chk[idx] = false;
for (pii& p : dist[idx]) {
int d = p.first;
int from = p.second;
for (auto next : G[idx]) {
int to = next.first;
int cost = next.second;
bool has = false;
for (pii& a : dist[to]) {
if (a.second == from) {
has = true;
if (a.first > d + cost) {
a.first = d + cost;
if (!chk[to]) {
chk[to] = true;
que.push({ d + cost, to });
}
}
break;
}
}
if (!has) {
dist[to].push_back({ d + cost,from });
if (dist[to].size() > 11) {
auto it = std::max_element(dist[to].begin(), dist[to].end());
if (it->second != from) {
if (!chk[to]) {
chk[to] = true;
que.push({ d + cost, to });
}
}
dist[to].erase(it);
}
else {
if (!chk[to]) {
chk[to] = true;
que.push({ d + cost, to });
}
}
}
}
}
}
while (q--) {
int s, x;
scanf("%d%d", &s, &x);
int arr[10];
for (int i = 0; i < x; i++) {
scanf("%d", &arr[i]);
chk[arr[i]] = true;
}
for (pii& p : dist[s]) {
if (!chk[p.second]) {
printf("%d %d\n", p.second, p.first);
break;
}
}
for (int i = 0; i < x; i++) {
chk[arr[i]] = false;
}
}
}