Submission #28562

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

mart

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define K 11
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;

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 = 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:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i = 0; i < vt[a].size(); i++){
                ^
mart.cpp:19:26: warning: unused variable 'nd' [-Wunused-variable]
  int i, j, idx, a, d, s, nd, flag;
                          ^
mart.cpp: In function 'int main()':
mart.cpp:41: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:43:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
                  ^
mart.cpp:47: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:53: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:54: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	3 ms	14264 KB	Output is correct
9	Correct	69 ms	19396 KB	Output is correct
10	Correct	69 ms	19388 KB	Output is correct
11	Correct	36 ms	14936 KB	Output is correct
12	Correct	26 ms	14396 KB	Output is correct
13	Incorrect	929 ms	54488 KB	Output isn't correct
14	Halted	0 ms	0 KB	-