Submission #28574

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28574	2017-07-16T07:33:27 Z	뚜룹뚜룹뚜룹뚜스~><(#1151, chan492811)	Alternative Mart (FXCUP2_mart)	C++11	0 / 1	1126 ms	54488 KB

mart

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define K 14
using namespace std;

struct data{ int from, to, d; };
struct cmp{
	bool operator()(data d1, data d2){ if(d1.d == d2.d) return d1.from > d2.from; return d1.d > d2.d; }
};
int n, m, k, q;
int iarr[50010], arr[20];
data darr[50010][20];
vector <data> vt[50010];
priority_queue <data, vector<data>, cmp> pq;

bool compare(data d1, data d2){
	if(d1.d == d2.d) return d1.from < d2.from;
	return d1.d < d2.d;
}
void dijkstra(){
	int i, j, idx, a, d, s, nd, flag;
	data tmp;
	while(!pq.empty()){
		tmp = pq.top(); pq.pop();
		a = tmp.to; d = tmp.d; idx = tmp.from; flag = 0;
		if(iarr[a] >= K) continue;
		for(i = 0; i < iarr[a]; i++){
			if(darr[a][i].from == idx) flag = 1;
		}
		if(flag) continue;
		darr[a][iarr[a]++] = (data){idx, a, d};
		for(i = 0; i < vt[a].size(); i++){
			s = vt[a][i].to;
			if(iarr[s] >= K) continue; flag = 0;
			for(j = 0; j < iarr[s]; j++) if(darr[s][i].from == idx) flag = 1;
			if(flag) continue;
			pq.push((data){idx, s, d + vt[a][i].d});
		}
	}
}
int main(){
	int i, j, l, a, s, d, flag;
	scanf("%d %d %d %d", &n, &m, &k, &q);
	for(i = 0; i < k; i++){
		scanf("%d", &a);
		pq.push((data){a, a, 0});
	}
	for(i = 0; i < m; i++){
		scanf("%d %d %d", &a, &s, &d);
		vt[a].push_back((data){a, s, d});
		vt[s].push_back((data){s, a, d});
	}
	dijkstra();
	for(i = 1; i <= n; i++){
		sort(darr[i], darr[i] + iarr[i], compare);
	}
	for(i = 0; i < q; i++){
		scanf("%d %d", &a, &s);
		for(j = 0; j < s; j++) scanf("%d", &arr[j]);
		for(j = 0; j < iarr[a]; j++){
			flag = 0;
			for(l = 0; l < s; l++){
				if(arr[l] == darr[a][j].from) flag = 1;
			}
			if(!flag){ printf("%d %d\n", darr[a][j].from, darr[a][j].d); break;}
		}
	}
	return 0;
}

Compilation message

mart.cpp: In function 'void dijkstra()':
mart.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i = 0; i < vt[a].size(); i++){
                ^
mart.cpp:23:26: warning: unused variable 'nd' [-Wunused-variable]
  int i, j, idx, a, d, s, nd, flag;
                          ^
mart.cpp: In function 'int main()':
mart.cpp:45:38: 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:47:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^
mart.cpp:51:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &a, &s, &d);
                                ^
mart.cpp:60:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &s);
                         ^
mart.cpp:61:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(j = 0; j < s; j++) scanf("%d", &arr[j]);
                                              ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	14264 KB	Output is correct
2	Correct	0 ms	14264 KB	Output is correct
3	Correct	0 ms	14264 KB	Output is correct
4	Correct	0 ms	14264 KB	Output is correct
5	Correct	0 ms	14396 KB	Output is correct
6	Correct	0 ms	14396 KB	Output is correct
7	Correct	3 ms	14408 KB	Output is correct
8	Correct	0 ms	14264 KB	Output is correct
9	Correct	86 ms	19396 KB	Output is correct
10	Correct	63 ms	19388 KB	Output is correct
11	Correct	49 ms	14936 KB	Output is correct
12	Correct	29 ms	14396 KB	Output is correct
13	Incorrect	1126 ms	54488 KB	Output isn't correct
14	Halted	0 ms	0 KB	-