제출 #28637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
28637		Official Fan of ACG (#68)	Alternative Mart (FXCUP2_mart)	C++14	1 / 1	3349 ms	39448 KiB

mart

#include<cstdio>
#include<algorithm>
#include<queue>
#include<functional>
#include<set>
#include<iterator>
using namespace std;

const int INF = 0x3fFFffFF;
const int NMAX = 50000, KMAX = 11;
typedef pair<int, int> pii;
typedef pair<pii, int> tri;
set<pii> dp[NMAX + 1];
vector<pii> g[NMAX + 1];
vector<int> S;

int main() {
	int N, M, K, Q; scanf("%d%d%d%d", &N, &M, &K, &Q);
	for (int i = 0; i < K; i++) {
		int x; scanf("%d", &x); S.push_back(x);
	}

	for (int i = 0; i < M; i++) {
		int u, v, w; scanf("%d%d%d", &u, &v, &w);
		g[u].push_back({ v,w });
		g[v].push_back({ u,w });
	}

	priority_queue<tri, vector<tri>, greater<tri>> pq;
	for (int s : S) {
		pq.push(tri(pii(0, s), s));
		dp[s].insert(pii(0, s));
	}
	while (!pq.empty()) {
		auto t = pq.top(); pq.pop();
		int here = t.second;
		int cost = t.first.first, from = t.first.second;
		if (dp[here].count({ cost,from })) {
			for (auto edge : g[here]) {
				int there = edge.first, ncost = edge.second + cost;
				pii nstate = { ncost, from };
				bool ok = dp[there].size() < KMAX || nstate < (*dp[there].rbegin());
				bool coin = false;
				for (const auto& p : dp[there]) if (p.second == from) {
					if (p.first <= ncost) ok = false;
					else coin = true;
				}
				if (ok) {
					dp[there].insert(nstate);
					if (coin) {
						for (auto it = dp[there].begin(); it != dp[there].end(); it++) {
							if (it->second == from && (*it) != nstate) {
								dp[there].erase(it);
								break;
							}
						}
					}
					if (dp[there].size() > KMAX) dp[there].erase(prev(dp[there].end()));
					pq.push(tri(pii(ncost, from), there));
				}
			}
		}
	}

	for (int q = 0; q < Q; q++) {
		int st, X; scanf("%d%d", &st, &X);
		set<int> fails;
		for (int i = 0; i < X; i++) {
			int f; scanf("%d", &f); fails.insert(f);
		}

		for (const auto& p : dp[st]) if (!fails.count(p.second)) {
			printf("%d %d\n", p.second, p.first); break;
		}
	}
}

컴파일 시 표준 에러 (stderr) 메시지

mart.cpp: In function 'int main()':
mart.cpp:18:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M, K, Q; scanf("%d%d%d%d", &N, &M, &K, &Q);
                                                   ^
mart.cpp:20:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x); S.push_back(x);
                         ^
mart.cpp:24:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d%d%d", &u, &v, &w);
                                           ^
mart.cpp:66:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int st, X; scanf("%d%d", &st, &X);
                                    ^
mart.cpp:69:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int f; scanf("%d", &f); fails.insert(f);
                          ^

• Subtask 1: 1 / 1