Submission #28795

#	Time	Username	Problem	Language	Result	Execution time	Memory
28795		kajebiii	Alternative Mart (FXCUP2_mart)	C++14	1 / 1	1263 ms	43152 KiB

mart

#include <stdio.h>
#include <bits/stdc++.h>
 
using namespace std;
 
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi; typedef pair<ll, int> pli; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
 
const int MAX_N = 5e4 + 100;
 
int N, M, K, Qn;
vector<int> Ks;
vector<pi> Ed[MAX_N];
int Chk[MAX_N];
int main() {
	cin >> N >> M >> K >> Qn;
	for(int i=0; i<K; i++) {int x; scanf("%d", &x); x--; Ks.push_back(x);}
	for(int i=0; i<M; i++) {
		int x, y, c; scanf("%d%d%d", &x, &y, &c); x--; y--;
		Ed[x].push_back(pi(y, c));
		Ed[y].push_back(pi(x, c));
	}
	vector<vector<pi>> dis(11, vector<pi>(N, pi(INF, -1)));
	vector<vector<int>> mar(N, vector<int>());
	vector<int> cnt(N, 0);
	priority_queue<ti, vector<ti>, greater<ti>> Q;
	for(int k : Ks) {
		Q.push(ti(0, k, k));
		dis[0][k] = pi(0, k);
	}
	while(!Q.empty()) {
		int d, v, wh; tie(d, v, wh) = Q.top(); Q.pop();
		if(cnt[v] >= 11) continue;
		bool isCan = true; for(int i=0; i<cnt[v]; i++) if(mar[v][i] == wh) {isCan = false; break;}
		if(!isCan) continue;
//		printf("%d %d %d\n", d, v, wh);
		mar[v].push_back(wh);
		dis[cnt[v]][v] = pi(d, wh); cnt[v]++;
 
		for(pi &e : Ed[v]) {
			int w, c; tie(w, c) = e;
			if(cnt[w] >= 11) continue;
			Q.push(ti(d+c, w, wh));
//			printf("push %d %d %d\n", d+c, w, wh);
		}
	}
 
	for(int q=1; q<=Qn; q++) {
		int s, k;
		scanf("%d%d", &s, &k); s--;
		for(int i=0; i<k; i++) {
			int x; scanf("%d", &x); x--;
			Chk[x] = q;
		}
		for(int i=0; i<11; i++) {
			if(Chk[mar[s][i]] != q) {
				printf("%d %d\n", dis[i][s].two+1, dis[i][s].one);
				break;
			}
		}
	}
	return 0;
}

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:24:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<K; i++) {int x; scanf("%d", &x); x--; Ks.push_back(x);}
                                                ^
mart.cpp:26:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, c; scanf("%d%d%d", &x, &y, &c); x--; y--;
                                           ^
mart.cpp:57:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &k); s--;
                        ^
mart.cpp:59:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x); x--;
                          ^

• Subtask 1: 1 / 1