Submission #22447

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22447	2017-04-30T04:48:18 Z	도치피치피보족(#942, lyzqm123)	Logistical Metropolis (KRIII5_LM)	C++14	2 / 7	2000 ms	36652 KB

LM

#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
typedef pair<int, long long> P;
vector<P> vec[100001];
int visit[100001] = { 0 };
long long solve(int index){
	long long ans = 0;
	queue<P> q;
	priority_queue<P, vector<P>, greater<P> > pq;

	visit[index] = 1;
	for (auto i : vec[index]){
		q.push(i);
		visit[i.second] = 1;
		ans += i.first;
	}
	while (!q.empty()){
		for (auto next : vec[q.front().second])
			pq.push(next);
		q.pop();
	}
	while (!pq.empty()){
		long long cost = pq.top().first;
		int curr = pq.top().second;
		pq.pop();
		if (visit[curr]) continue;
		visit[curr] = 1;
		ans += cost;
		for (auto next : vec[curr]) pq.push(next);
	}
	return ans;
}
int main(){
	int N, M;
	scanf("%d%d", &N, &M);
	for (int m = 0; m < M; m++){
		int s, e;
		long long v;
		scanf("%d%d%d", &s, &e, &v);
		vec[s].push_back({ v, e });
		vec[e].push_back({ v, s });
	}

	for (int n = 1; n <= N; n++){
		for (int v = 1; v <= N; v++) visit[v] = 0;
		printf("%lld\n",solve(n));
	}
	return 0;
}

Compilation message

LM.cpp: In function 'int main()':
LM.cpp:42:29: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
   scanf("%d%d%d", &s, &e, &v);
                             ^
LM.cpp:38:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
LM.cpp:42: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);
                              ^

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	809 ms	4932 KB	Output is correct
2	Correct	819 ms	4932 KB	Output is correct
3	Correct	816 ms	4936 KB	Output is correct
4	Correct	819 ms	4936 KB	Output is correct
5	Correct	816 ms	4932 KB	Output is correct
6	Correct	849 ms	5056 KB	Output is correct
7	Correct	823 ms	4936 KB	Output is correct
8	Correct	863 ms	5064 KB	Output is correct
9	Correct	839 ms	5064 KB	Output is correct
10	Correct	873 ms	4936 KB	Output is correct
11	Correct	1039 ms	4944 KB	Output is correct
12	Correct	953 ms	5044 KB	Output is correct
13	Correct	993 ms	5040 KB	Output is correct
14	Correct	966 ms	5044 KB	Output is correct
15	Correct	973 ms	5048 KB	Output is correct
16	Correct	846 ms	5040 KB	Output is correct
17	Correct	829 ms	5032 KB	Output is correct
18	Correct	786 ms	5032 KB	Output is correct
19	Correct	806 ms	5032 KB	Output is correct
20	Correct	796 ms	5028 KB	Output is correct
21	Correct	799 ms	5040 KB	Output is correct
22	Correct	786 ms	5032 KB	Output is correct
23	Correct	789 ms	5028 KB	Output is correct
24	Correct	843 ms	5032 KB	Output is correct
25	Correct	0 ms	4668 KB	Output is correct
26	Correct	0 ms	4668 KB	Output is correct
27	Correct	3 ms	4668 KB	Output is correct
28	Correct	126 ms	4800 KB	Output is correct

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2000 ms	36652 KB	Execution timed out
2	Halted	0 ms	0 KB	-