Submission #28574

#	Time	Username	Problem	Language	Result	Execution time	Memory
28574		뚜룹뚜룹뚜룹뚜스~>< (#68)	Alternative Mart (FXCUP2_mart)	C++11	0 / 1	1126 ms	54488 KiB

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 (stderr)

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