Submission #71613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
71613	2018-08-25T08:36:20 Z	노영훈(#2218)	Logistical Metropolis (KRIII5_LM)	C++11	2 / 7	336 ms	8112 KB

LM

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

struct edge{
	int u,v,c;
	bool operator < (const edge & e) const {
		return c<e.c;
	}
};
vector<edge> E;
int n,m;
int U[2010];
int find(int x){ return x==U[x] ? x : U[x]=find(U[x]); }
void unite(int x, int y){ U[find(y)]=find(x); }

void solve(int s){
	vector<edge> F;
	iota(U, U+n+1, 0);
	long long ans=0;
	for(edge &e:E){
		int u=e.u, v=e.v, c=e.c;
		if(u==s || v==s) unite(u,v), ans+=c;
		else F.push_back(e);
	}
	sort(F.begin(), F.end());
	for(edge &e:F){
		int u=e.u, v=e.v, c=e.c;
		if(find(u)==find(v)) continue;
		unite(u,v); ans+=c;
	}
	cout<<ans<<'\n';
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=1; i<=m; i++){
		int u,v,c; cin>>u>>v>>c;
		E.push_back({u,v,c});
	}
	for(int i=1; i<=n; i++) solve(i);
	return 0;
}

Subtask #1

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	316 ms	504 KB	Output is correct
2	Correct	303 ms	584 KB	Output is correct
3	Correct	307 ms	664 KB	Output is correct
4	Correct	318 ms	684 KB	Output is correct
5	Correct	330 ms	832 KB	Output is correct
6	Correct	297 ms	832 KB	Output is correct
7	Correct	336 ms	832 KB	Output is correct
8	Correct	324 ms	872 KB	Output is correct
9	Correct	329 ms	872 KB	Output is correct
10	Correct	311 ms	872 KB	Output is correct
11	Correct	273 ms	908 KB	Output is correct
12	Correct	293 ms	908 KB	Output is correct
13	Correct	299 ms	912 KB	Output is correct
14	Correct	289 ms	932 KB	Output is correct
15	Correct	295 ms	932 KB	Output is correct
16	Correct	263 ms	952 KB	Output is correct
17	Correct	291 ms	960 KB	Output is correct
18	Correct	285 ms	960 KB	Output is correct
19	Correct	262 ms	960 KB	Output is correct
20	Correct	273 ms	960 KB	Output is correct
21	Correct	301 ms	960 KB	Output is correct
22	Correct	262 ms	960 KB	Output is correct
23	Correct	293 ms	960 KB	Output is correct
24	Correct	270 ms	960 KB	Output is correct
25	Correct	2 ms	960 KB	Output is correct
26	Correct	3 ms	960 KB	Output is correct
27	Correct	3 ms	960 KB	Output is correct
28	Correct	79 ms	960 KB	Output is correct

Subtask #2

0 / 72.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	154 ms	8112 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-