Submission #26987

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26987	2017-07-08T07:37:29 Z	검수팍(#1115)	Alternative Mart (FXCUP2_mart)	C++	0 / 1	5000 ms	135872 KB

mart

#include<stdio.h>
#include<memory.h>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;

struct nod {
	int st, ix, dst;
	nod(int st_, int ix_, int dst_){ st=st_, ix=ix_, dst=dst_; }
	bool operator< (const nod& c) const {
		if(dst != c.dst) return dst > c.dst;
		return st > c.st;
	}
};

priority_queue<nod> pq;

int N, M, K, Q;
int endp[406060], val[406060], prv[406060], top[101010], ecn;
int dist[101010][11], dnum[101010][11], dcn[101010];
set<pair<int,int> > chk;
map<pair<int,int>, int> mp;

void edge(int s, int e, int v){
	endp[ecn]=e, val[ecn]=v, prv[ecn]=top[s], top[s]=ecn++;
}

int get_dist(int s, int e){
	if(mp.find(make_pair(s,e)) == mp.end()) return 2e9;
	return mp[make_pair(s,e)];
}

int st, x, close[11], ban[101010];

int main(){
	scanf("%d%d%d%d", &N, &M, &K, &Q);
	for(int i=1; i<=N; i++) top[i]=-1;
	memset(dist, 0x3f, sizeof(dist));
	for(int i=K; i--;){
		int a; scanf("%d", &a);
		pq.push(nod(a, a, 0));
		mp[make_pair(a, a)] = 0;
	}
	for(int i=M; i--;){
		int s, e, v;
		scanf("%d%d%d", &s, &e, &v);
		edge(s, e, v), edge(e, s, v);
	}
	while(!pq.empty()){
		nod cur = pq.top(); pq.pop();
		if(dcn[cur.ix] >= 11) continue;
		if(chk.find(make_pair(cur.ix, cur.st)) != chk.end()) continue;
		int dix = dcn[cur.ix];
		dist[cur.ix][dix] = cur.dst, dnum[cur.ix][dix] = cur.st, dcn[cur.ix]++;
		chk.insert(make_pair(cur.ix, cur.st));
		for(int i=top[cur.ix]; i>=0; i=prv[i]){
			if(cur.dst+val[i] >= get_dist(cur.st, endp[i])) continue;
			mp[make_pair(cur.st, endp[i])] = cur.dst+val[i];
			pq.push(nod(cur.st, endp[i], cur.dst+val[i]));
		}
	}

	for(int t=Q; t--;){
		scanf("%d%d", &st, &x);
		for(int i=0; i<x; i++) scanf("%d", &close[i]), ban[close[i]]=1;
		for(int i=0; i<=10; i++){
			if(ban[dnum[st][i]]) continue;
			printf("%d %d\n", dnum[st][i], dist[st][i]);
			break;
		}
		for(int i=0; i<x; i++) ban[close[i]]=0;
	}
	return 0;
}

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:38: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 a; scanf("%d", &a);
                         ^
mart.cpp:48:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &s, &e, &v);
                              ^
mart.cpp:66:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &st, &x);
                         ^
mart.cpp:67:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0; i<x; i++) scanf("%d", &close[i]), ban[close[i]]=1;
                                                                 ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	16560 KB	Output is correct
2	Correct	0 ms	16560 KB	Output is correct
3	Correct	3 ms	16560 KB	Output is correct
4	Correct	0 ms	16560 KB	Output is correct
5	Correct	3 ms	16692 KB	Output is correct
6	Correct	3 ms	16692 KB	Output is correct
7	Correct	6 ms	17220 KB	Output is correct
8	Correct	9 ms	17220 KB	Output is correct
9	Correct	163 ms	21600 KB	Output is correct
10	Correct	63 ms	17152 KB	Output is correct
11	Correct	159 ms	22724 KB	Output is correct
12	Correct	146 ms	22632 KB	Output is correct
13	Correct	3136 ms	112792 KB	Output is correct
14	Correct	2879 ms	135872 KB	Output is correct
15	Correct	213 ms	22144 KB	Output is correct
16	Correct	179 ms	22104 KB	Output is correct
17	Correct	2819 ms	72068 KB	Output is correct
18	Correct	2036 ms	71208 KB	Output is correct
19	Correct	3656 ms	78336 KB	Output is correct
20	Correct	2863 ms	76752 KB	Output is correct
21	Correct	3479 ms	78568 KB	Output is correct
22	Correct	2593 ms	77160 KB	Output is correct
23	Correct	2733 ms	84396 KB	Output is correct
24	Correct	3193 ms	82728 KB	Output is correct
25	Correct	3003 ms	86112 KB	Output is correct
26	Correct	3223 ms	84576 KB	Output is correct
27	Correct	273 ms	22192 KB	Output is correct
28	Correct	256 ms	22116 KB	Output is correct
29	Correct	3989 ms	72852 KB	Output is correct
30	Correct	2833 ms	72000 KB	Output is correct
31	Correct	4053 ms	89456 KB	Output is correct
32	Correct	3563 ms	81888 KB	Output is correct
33	Correct	3943 ms	87452 KB	Output is correct
34	Correct	4686 ms	110280 KB	Output is correct
35	Correct	3279 ms	100140 KB	Output is correct
36	Correct	4029 ms	107928 KB	Output is correct
37	Correct	4526 ms	117564 KB	Output is correct
38	Correct	4343 ms	112020 KB	Output is correct
39	Correct	319 ms	22392 KB	Output is correct
40	Correct	313 ms	22468 KB	Output is correct
41	Correct	4089 ms	74300 KB	Output is correct
42	Correct	4669 ms	74384 KB	Output is correct
43	Execution timed out	5000 ms	113280 KB	Execution timed out
44	Halted	0 ms	0 KB	-