Submission #28588

#	Time	Username	Problem	Language	Result	Execution time	Memory
28588		볼빨간 승관이 (#68)	Alternative Mart (FXCUP2_mart)	C++11	1 / 1	843 ms	15504 KiB

mart

#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;
		}
		std::sort(dist[s].begin(), dist[s].end());
		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;
		}
	}
}

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:26:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &m, &k, &q);
                                   ^
mart.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^
mart.cpp:36:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a, &b, &c);
                              ^
mart.cpp:92:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &x);
                        ^
mart.cpp:95:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &arr[i]);
                        ^

• Subtask 1: 1 / 1