답안 #28579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
28579	2017-07-16T07:36:03 Z	쥬니님일어나세요 버스운전해주시기로했잖아요(#1179, kjp4155, pjh0123, dnsdhrj)	Alternative Mart (FXCUP2_mart)	C++14	0 / 1	5000 ms	163552 KB

mart

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll,ll> Pll;

#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 repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()

#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define INF 987654321
#define IINF 87654321987654321
#define MAXV 200500


#define MOD 1234567
int N,M,K,T;
vector<int> pos;
vector<Pll> E[60000];
ll dist[60000]; int pa[60000];
bool vis[60000];
set<int> used[60000];
set<Pll> s[60000];
typedef pair<ll,Pll> ppll;
int main(){
	rep(i,60000) dist[i] = IINF;
	geti(N,M,K,T);
	repp(i,K){
		int x; geti(x); pos.pb(x);
	}

	repp(i,M){
		ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
		E[a].push_back({b,c}); E[b].push_back({a,c});
	}

	priority_queue<ppll, vector<ppll>, greater<ppll>> pq;
	
	for(auto e : pos){
		pq.push({0,{e,e}}); dist[e] = 0; vis[e] =true;
		pa[e] = e; used[e].insert(e);
		s[e].insert({0,e});
	}

	while(!pq.empty()){
		ll curd = pq.top().Fi; int cur = pq.top().Se.Fi;
		int p = pq.top().Se.Se;
		if( used[cur].find(p) == used[cur].end() ){
			used[cur].insert(p);
			s[cur].insert({curd,p});
		}
		pq.pop();
		
		for(auto e : E[cur]){
			if( used[e.Fi].size() >= 11 ) continue;
			if( used[e.Fi].find( p ) != used[e.Fi].end() ) continue;
			//used[e.Fi].insert(p);
			//s[e.Fi].insert({curd+e.Se,p});
			pq.push({curd+e.Se,{e.Fi,p}});
		}
	} 

	/*
	repp(i,N){
		for(auto e : s[i]){
			cout << i << " " << e.Fi << " " << e.Se << endl;
		}
	}
*/
	//cout << T << endl;
	repp(i,T){
		int S; geti(S);
		int X; geti(X);
		set<int> die;
		repp(i,X){
			int y; geti(y); die.insert(y);
		}
		//for(auto e : die) printf("[%d]",e);
		bool ok = false;
		for(auto e : s[S]){
			if( die.find(e.Se) == die.end() ){
				printf("%lld %lld\n",e.Se,e.Fi);
				//printf("!");
				ok = true;
				break;
			}
		
		}

	}





}	

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:107:8: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   bool ok = false;
        ^
mart.cpp:55:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  geti(N,M,K,T);
               ^
mart.cpp:57:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; geti(x); pos.pb(x);
                 ^
mart.cpp:61:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
                                           ^
mart.cpp:100:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int S; geti(S);
                 ^
mart.cpp:101:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int X; geti(X);
                 ^
mart.cpp:104:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int y; geti(y); die.insert(y);
                  ^

Subtask #1

0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	9820 KB	Output is correct
2	Correct	3 ms	9820 KB	Output is correct
3	Correct	0 ms	9820 KB	Output is correct
4	Correct	3 ms	9820 KB	Output is correct
5	Correct	6 ms	9956 KB	Output is correct
6	Correct	6 ms	9956 KB	Output is correct
7	Correct	3 ms	10620 KB	Output is correct
8	Correct	6 ms	10480 KB	Output is correct
9	Correct	376 ms	29700 KB	Output is correct
10	Correct	326 ms	19948 KB	Output is correct
11	Correct	89 ms	17652 KB	Output is correct
12	Correct	76 ms	16156 KB	Output is correct
13	Execution timed out	5000 ms	163552 KB	Execution timed out
14	Halted	0 ms	0 KB	-