oj.uz

답안 #29054

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29054 2017-07-18T07:48:54 Z cki86201 Alternative Mart (FXCUP2_mart) C++11
0 / 1
 5000 ms 106512 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];
map <int, int> 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) pq.push(t3(0, e, e)), M[e][e] = 0;
	int cnt[50050] = {};
	while(!pq.empty()) {
		t3 t = pq.top(); pq.pop();
		int v = get<1>(t), s = get<2>(t);
		int L = get<0>(t);
		if(M[v][s] != L) continue;
		if(cnt[v] > 11) continue;
		++cnt[v];
		
		for(pii e : E[v]) {
			if(M[e.Se].find(s) == M[e.Se].end()) {
				M[e.Se][s] = L + e.Fi;
				pq.push(t3(L + e.Fi, e.Se, s));
			}
			else if(M[e.Se][s] > L + e.Fi) {
				M[e.Se][s] = L + e.Fi;
				pq.push(t3(L + e.Fi, e.Se, s));
			}
		}
	}
	while(q--) {
		int s, r; scanf("%d%d", &s, &r);
		set <int> v;
		rep(a, r) {
			int x; scanf("%d", &x); v.insert(x);
		}
		pii ans = pii(2e9, -1);
		for(pii e : M[s]) if(v.find(e.Fi) == v.end() && ans.Fi > e.Se) ans.Fi = e.Se, ans.Se = e.Fi;
		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:73: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:76:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x); v.insert(x);
                          ^

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5616 KB Output is correct
2 Correct 0 ms 5620 KB Output is correct
3 Correct 0 ms 5612 KB Output is correct
4 Correct 3 ms 5616 KB Output is correct
5 Correct 0 ms 5620 KB Output is correct
6 Correct 0 ms 5612 KB Output is correct
7 Correct 3 ms 6012 KB Output is correct
8 Correct 3 ms 5880 KB Output is correct
9 Correct 156 ms 10196 KB Output is correct
10 Correct 16 ms 6424 KB Output is correct
11 Correct 56 ms 8884 KB Output is correct
12 Correct 56 ms 8652 KB Output is correct
13 Correct 4983 ms 86208 KB Output is correct
14 Execution timed out 5000 ms 106512 KB Execution timed out
15 Halted 0 ms 0 KB -