Submission #28566

# Submission time Handle Problem Language Result Execution time Memory
28566 2017-07-16T07:26:57 Z 쥬니님일어나세요 버스운전해주시기로했잖아요(#1179, kjp4155, pjh0123, dnsdhrj) Alternative Mart (FXCUP2_mart) C++14
0 / 1
3 ms 9960 KB
#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){
		int a,b,c; geti(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;
		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;
		}
	}
*/
	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);
		for(auto e : s[S]){
			if( die.find(e.Se) == die.end() ){
				printf("%lld %lld\n",e.Se,e.Fi);
				break;
			}
		}

	}





}	

Compilation message

mart.cpp: In function 'int main()':
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:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b,c; geti(a,b,c);
                         ^
mart.cpp:95:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int S; geti(S);
                 ^
mart.cpp:96:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int X; geti(X);
                 ^
mart.cpp:99: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);
                  ^
# Verdict Execution time Memory 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 Incorrect 0 ms 9960 KB Output isn't correct
6 Halted 0 ms 0 KB -