oj.uz

답안 #22447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22447 2017-04-30T04:48:18 Z 도치피치피보족(#942, lyzqm123) Logistical Metropolis (KRIII5_LM) C++14
2 / 7
 2000 ms 36652 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 36652 KB Execution timed out
2 Halted 0 ms 0 KB -