oj.uz

답안 #29051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29051 2017-07-18T07:44:51 Z cki86201 Alternative Mart (FXCUP2_mart) C++11
0 / 1
 5000 ms 130272 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];
set <pii> S[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)), S[e].insert(pii(0, 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;
				S[e.Se].insert(pii(L + e.Fi, s));
				pq.push(t3(L + e.Fi, e.Se, s));
			}
			else if(M[e.Se][s] > L + e.Fi) {
				S[e.Se].erase(pii(M[e.Se][s], s));
				S[e.Se].insert(pii(L + e.Fi, s));
				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);
		}
		for(pii e : S[s]) if(v.find(e.Se) == v.end()) {
			printf("%d %d\n", e.Se, e.Fi);
			break;
		}
	}
}

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:41: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:43: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:47: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:77: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:80: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 7960 KB Output is correct
2 Correct 3 ms 7964 KB Output is correct
3 Correct 0 ms 7968 KB Output is correct
4 Correct 0 ms 7964 KB Output is correct
5 Correct 0 ms 8100 KB Output is correct
6 Correct 3 ms 8100 KB Output is correct
7 Correct 6 ms 8620 KB Output is correct
8 Correct 3 ms 8628 KB Output is correct
9 Correct 216 ms 14456 KB Output is correct
10 Correct 29 ms 8900 KB Output is correct
11 Correct 76 ms 14032 KB Output is correct
12 Correct 79 ms 13772 KB Output is correct
13 Execution timed out 5000 ms 130272 KB Execution timed out
14 Halted 0 ms 0 KB -