Submission #28500

#	Time	Username	Problem	Language	Result	Execution time	Memory
28500		三( ε:) (#68)	Alternative Mart (FXCUP2_mart)	C++14	0 / 1	2426 ms	46032 KiB

mart

#include <cstdio>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<ll, ii> lii;

int main() {
	//freopen("input.txt", "r", stdin);
	int n, m, k, q;
	scanf("%d%d%d%d", &n, &m, &k, &q);
	vector<set<li>> dist(n); // (distance, from)
	vector<vector<ii>> adj(n); // (destination, weight)
	priority_queue<lii> pq; // (-distance, (here, from))
	while (k--) {
		int s;
		scanf("%d", &s);
		--s;
		dist[s].emplace(0ll, s);
		pq.emplace(0ll, ii(s, s));
	}
	while (m--) {
		int p, q, v;
		scanf("%d%d%d", &p, &q, &v);
		--p; --q;
		adj[p].emplace_back(q, v);
		adj[q].emplace_back(p, v);
	}
	while (!pq.empty()) {
		ll weight = -pq.top().first;
		int here = pq.top().second.first;
		int from = pq.top().second.second;
		pq.pop();
		bool skip = false;
		bool hasFrom = false;
		for (li p : dist[here]) {
			if (p.second != from)
				continue;
			hasFrom = true;
			if (weight > p.first)
				skip = true;
			break;
		}
		if (skip || !hasFrom) continue;
		for (ii p : adj[here]) {
			int next = p.first;
			ll nweight = weight + p.second;
			bool skip = false;
			bool hasFrom = false;
			for (auto it = dist[next].begin(); it != dist[next].end(); ++it) {
				if (it->second != from) continue;
				hasFrom = true;
				if (it->first <= nweight)
					skip = true;
				else
					dist[next].erase(it);
				break;
			}
			if (!hasFrom && dist[next].size() >= 11) {
				if (dist[next].rbegin()->first <= nweight)
					skip = true;
				else
					dist[next].erase(--dist[next].end());
			}
			if (skip) continue;
			dist[next].emplace(nweight, from);
			pq.emplace(-nweight, ii(next, from));
		}
	}
	while (q--) {
		int target, x;
		scanf("%d%d", &target, &x);
		--target;
		set<int> closed;
		while (x--) {
			int c;
			scanf("%d", &c);
			closed.insert(--c);
		}
		for (li p : dist[target]) {
			if (closed.find(p.second) == closed.end()) {
				printf("%d %lld\n", p.second + 1, p.first);
				break;
			}
		}
	}
	return 0;
}

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:14: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:20:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s);
                  ^
mart.cpp:27:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &p, &q, &v);
                              ^
mart.cpp:75:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &target, &x);
                             ^
mart.cpp:80:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &c);
                   ^

• Subtask 1: 0 / 1