oj.uz

답안 #29083

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29083 2017-07-18T08:11:41 Z cki86201 Alternative Mart (FXCUP2_mart) C++11
1 / 1
 1293 ms 44012 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;

int n, m, k, q;
vector <int> mart;
vector <pii> E[50050];
vector <pii> M[50050];

void solve() {
	scanf("%d%d%d%d", &n, &m, &k, &q);
	rep(i, k) {
		int x; scanf("%d", &x);
		mart.pb(x);
	}
	rep(i, m) {
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		E[x].pb(pii(z, y));
		E[y].pb(pii(z, x));
	}
	priority_queue <t3, vector<t3>, greater<t3> > pq;
	for(int e : mart) {
		M[e].pb(pii(0, e));
		pq.push(t3(0, e, e));
	}
	while(!pq.empty()) {
		t3 t = pq.top(); pq.pop();
		int v = get<1>(t), s = get<2>(t);
		int L = get<0>(t);
		int ok = 0;
		for(pii e : M[v]) if(e.Fi == L && e.Se == s){ ok = 1; break; }
		if(ok == 0) continue;
		
		for(pii e : E[v]) {
			int flag = 0;
			for(pii &f : M[e.Se]) if(f.Se == s) {
				flag = 1;
				if(f.Fi > L + e.Fi) {
					f.Fi = L + e.Fi;
					pq.push(t3(L + e.Fi, e.Se, s));
					sort(all(M[e.Se]));
				}
				break;
			}
			if(flag == 0) {
				M[e.Se].pb(pii(L + e.Fi, s));
				for(int i=sz(M[e.Se])-1;i;i--) {
					if(M[e.Se][i-1] > M[e.Se][i]) swap(M[e.Se][i], M[e.Se][i-1]);
					else break;
				}
				if(sz(M[e.Se]) > 11) M[e.Se].pop_back();
				pq.push(t3(L + e.Fi, e.Se, s));
			}
		}
	}
	int chk[50050] = {};
	while(q--) {
		int s, r; scanf("%d%d", &s, &r);
		rep(a, r) {
			int x; scanf("%d", &x); chk[x] = q + 10;
		}
		pii ans = pii(2e9, -1);
		//for(pii e : M[s]) printf("%d,%d\n", e.Fi, e.Se); puts("");
		for(pii e : M[s]) if(chk[e.Se] != q + 10 && ans > e) ans.Fi = e.Fi, ans.Se = e.Se;
		printf("%d %d\n", ans.Se, ans.Fi);
	}
}

int main(){
	int tc = 1; // scanf("%d", &tc);
	for(int t=1;t<=tc;t++) {
		solve();
	}
	return 0;
};

Compilation message

mart.cpp: In function 'void solve()':
mart.cpp:40: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:42:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
                         ^
mart.cpp:46:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d%d%d", &x, &y, &z);
                                           ^
mart.cpp:87:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, r; scanf("%d%d", &s, &r);
                                  ^
mart.cpp:89:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x); chk[x] = q + 10;
                          ^

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 4440 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4436 KB Output is correct
4 Correct 0 ms 4440 KB Output is correct
5 Correct 0 ms 4436 KB Output is correct
6 Correct 0 ms 4436 KB Output is correct
7 Correct 0 ms 4572 KB Output is correct
8 Correct 3 ms 4572 KB Output is correct
9 Correct 69 ms 9524 KB Output is correct
10 Correct 9 ms 5188 KB Output is correct
11 Correct 29 ms 5516 KB Output is correct
12 Correct 19 ms 5496 KB Output is correct
13 Correct 726 ms 44012 KB Output is correct
14 Correct 836 ms 44012 KB Output is correct
15 Correct 109 ms 8004 KB Output is correct
16 Correct 116 ms 7608 KB Output is correct
17 Correct 513 ms 14776 KB Output is correct
18 Correct 366 ms 13812 KB Output is correct
19 Correct 523 ms 15296 KB Output is correct
20 Correct 436 ms 13948 KB Output is correct
21 Correct 603 ms 15380 KB Output is correct
22 Correct 499 ms 13956 KB Output is correct
23 Correct 699 ms 17384 KB Output is correct
24 Correct 626 ms 15688 KB Output is correct
25 Correct 713 ms 17384 KB Output is correct
26 Correct 623 ms 15824 KB Output is correct
27 Correct 103 ms 8368 KB Output is correct
28 Correct 96 ms 7928 KB Output is correct
29 Correct 666 ms 16016 KB Output is correct
30 Correct 539 ms 14848 KB Output is correct
31 Correct 686 ms 17048 KB Output is correct
32 Correct 613 ms 14584 KB Output is correct
33 Correct 716 ms 17016 KB Output is correct
34 Correct 1008 ms 21868 KB Output is correct
35 Correct 933 ms 21544 KB Output is correct
36 Correct 929 ms 22172 KB Output is correct
37 Correct 1126 ms 21432 KB Output is correct
38 Correct 1153 ms 22088 KB Output is correct
39 Correct 156 ms 8792 KB Output is correct
40 Correct 139 ms 8796 KB Output is correct
41 Correct 766 ms 17944 KB Output is correct
42 Correct 739 ms 17948 KB Output is correct
43 Correct 1163 ms 21064 KB Output is correct
44 Correct 1183 ms 21600 KB Output is correct
45 Correct 996 ms 20808 KB Output is correct
46 Correct 1163 ms 21464 KB Output is correct
47 Correct 1293 ms 32604 KB Output is correct
48 Correct 1153 ms 33116 KB Output is correct
49 Correct 896 ms 32736 KB Output is correct
50 Correct 1033 ms 33116 KB Output is correct
51 Correct 963 ms 32996 KB Output is correct
52 Correct 876 ms 33244 KB Output is correct
53 Correct 259 ms 13016 KB Output is correct
54 Correct 1043 ms 17220 KB Output is correct
55 Correct 1008 ms 21088 KB Output is correct
56 Correct 956 ms 20924 KB Output is correct
57 Correct 299 ms 15868 KB Output is correct