Submission #842552
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second struct edge{int to,cost,id;}; vector<edge> G[100]; int C[100][100]={0}; int main() { int n,m,k; cin >>n >>m >>k; rep(i,m) { int f,t,c; cin >>f >>t >>c; --f; --t; G[f].pb(edge{t,c,i}); G[t].pb(edge{f,c,i}); C[f][t]=C[t][f]=c; } int g=0; //閉路に含まれない辺,含まれる辺 vector<int> x,y; vector<bool> vis(n); vector<bool> use(m); vector<int> par(n,-1); rep(i,n) { if(vis[i]) continue; ++g; vis[i]=true; par[i]=i; int viscount=1; int va=-1, vb=-1; vector<int> cost, dist(n,0); queue<int> que; que.push(i); while(!que.empty()) { int v=que.front(); que.pop(); rep(j,G[v].size()) { edge e=G[v][j]; int nx=e.to; if(!use[e.id]) { use[e.id]=true; cost.pb(e.cost); if(!vis[nx]) { vis[nx]=true; que.push(nx); dist[nx]=dist[v]+1; par[nx]=v; ++viscount; } else { va=v; vb=nx; y.pb(e.cost); } } } } int COST=cost.size(); if(viscount==COST) { //閉路あり if(dist[va]>dist[vb]) { while(dist[va]>dist[vb]) { y.pb(C[va][par[va]]); va=par[va]; } } if(dist[va]<dist[vb]) { while(dist[va]<dist[vb]) { y.pb(C[vb][par[vb]]); vb=par[vb]; } } while(va!=vb) { y.pb(C[va][par[va]]); y.pb(C[vb][par[vb]]); va=par[va]; vb=par[vb]; } sort(all(cost)); sort(all(y)); int yidx=0; rep(cidx,COST) { if(cost[cidx]==y[yidx]) ++yidx; else x.pb(cost[cidx]); } } else for(auto &c:cost) x.pb(c); } sort(all(x)); sort(all(y)); // printf("X,Y %d, %d\n", x.size(), y.size()); int ans=0; if(g<k) { ans=123456789; if(k-g<=x.size()) { int tmp=0; rep(i,k-g) tmp+=x[i]; ans=min(ans,tmp); } if(y.size()>=3) { int tmp=y[0]+y[1]; vector<int> z(x); for(int i=2; i<y.size(); ++i) z.pb(y[i]); sort(all(z)); rep(i,k-g-1) tmp+=z[i]; ans=min(ans,tmp); } } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 独立記念日 |
User | imulan |
Language | C++11 (GCC 4.8.1) |
Score | 100 |
Code Size | 3513 Byte |
Status | AC |
Exec Time | 34 ms |
Memory | 1288 KB |
Judge Result
Set Name | nonloop | loop | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 70 / 70 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
nonloop | nonloop/case_000.txt, nonloop/case_001.txt, nonloop/case_002.txt, nonloop/case_003.txt, nonloop/case_004.txt, nonloop/case_005.txt, nonloop/case_006.txt, nonloop/case_007.txt, nonloop/case_008.txt, nonloop/case_009.txt, nonloop/case_010.txt, nonloop/case_011.txt, nonloop/case_012.txt, nonloop/case_013.txt, nonloop/case_014.txt, nonloop/case_015.txt, nonloop/case_016.txt, nonloop/case_017.txt, nonloop/case_018.txt, nonloop/case_019.txt, nonloop/case_020.txt, nonloop/case_021.txt, nonloop/case_022.txt, nonloop/case_023.txt, nonloop/case_024.txt, nonloop/case_025.txt, nonloop/case_026.txt, nonloop/case_027.txt, nonloop/case_028.txt, nonloop/case_029.txt, nonloop/case_030.txt, nonloop/case_031.txt, nonloop/case_032.txt, nonloop/case_033.txt |
loop | loop/case_000.txt, loop/case_001.txt, loop/case_002.txt, loop/case_003.txt, loop/case_004.txt, loop/case_005.txt, loop/case_006.txt, loop/case_007.txt, loop/case_008.txt, loop/case_009.txt, loop/case_010.txt, loop/case_011.txt, loop/case_012.txt, loop/case_013.txt, loop/case_014.txt, loop/case_015.txt, loop/case_016.txt, loop/case_017.txt, loop/case_018.txt, loop/case_019.txt, loop/case_020.txt, loop/case_021.txt, loop/case_022.txt, loop/case_023.txt, loop/case_024.txt, loop/case_025.txt, loop/case_026.txt, loop/case_027.txt, loop/case_028.txt, loop/case_029.txt, loop/case_030.txt, loop/case_031.txt, loop/case_032.txt, loop/case_033.txt, loop/loop_case_000.txt, loop/loop_case_001.txt, loop/loop_case_002.txt, loop/loop_case_003.txt, loop/loop_case_004.txt, loop/loop_case_005.txt, loop/loop_case_006.txt, loop/loop_case_007.txt, loop/loop_case_008.txt, loop/loop_case_009.txt, loop/loop_case_010.txt, loop/loop_case_011.txt, loop/loop_case_012.txt, loop/loop_case_013.txt, loop/loop_case_014.txt, loop/loop_case_015.txt, loop/loop_case_016.txt, loop/loop_case_017.txt, loop/loop_case_018.txt, loop/loop_case_019.txt, loop/loop_case_020.txt, loop/loop_case_021.txt, loop/loop_case_022.txt, loop/loop_case_023.txt, loop/loop_case_024.txt, loop/loop_case_025.txt, loop/loop_case_026.txt, loop/loop_case_027.txt, loop/loop_case_028.txt, loop/loop_case_029.txt, loop/loop_case_030.txt, loop/loop_case_031.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
loop/case_000.txt | AC | 34 ms | 1100 KB |
loop/case_001.txt | AC | 28 ms | 1168 KB |
loop/case_002.txt | AC | 29 ms | 1156 KB |
loop/case_003.txt | AC | 30 ms | 1148 KB |
loop/case_004.txt | AC | 29 ms | 1156 KB |
loop/case_005.txt | AC | 29 ms | 1172 KB |
loop/case_006.txt | AC | 27 ms | 1152 KB |
loop/case_007.txt | AC | 28 ms | 1136 KB |
loop/case_008.txt | AC | 33 ms | 1160 KB |
loop/case_009.txt | AC | 31 ms | 1100 KB |
loop/case_010.txt | AC | 28 ms | 1228 KB |
loop/case_011.txt | AC | 31 ms | 1172 KB |
loop/case_012.txt | AC | 29 ms | 1172 KB |
loop/case_013.txt | AC | 29 ms | 1172 KB |
loop/case_014.txt | AC | 31 ms | 1224 KB |
loop/case_015.txt | AC | 30 ms | 1164 KB |
loop/case_016.txt | AC | 30 ms | 1172 KB |
loop/case_017.txt | AC | 28 ms | 1228 KB |
loop/case_018.txt | AC | 30 ms | 1168 KB |
loop/case_019.txt | AC | 30 ms | 1172 KB |
loop/case_020.txt | AC | 29 ms | 1160 KB |
loop/case_021.txt | AC | 28 ms | 1156 KB |
loop/case_022.txt | AC | 29 ms | 1156 KB |
loop/case_023.txt | AC | 28 ms | 1156 KB |
loop/case_024.txt | AC | 30 ms | 1136 KB |
loop/case_025.txt | AC | 29 ms | 1252 KB |
loop/case_026.txt | AC | 29 ms | 1160 KB |
loop/case_027.txt | AC | 30 ms | 1168 KB |
loop/case_028.txt | AC | 29 ms | 1136 KB |
loop/case_029.txt | AC | 26 ms | 1176 KB |
loop/case_030.txt | AC | 30 ms | 1176 KB |
loop/case_031.txt | AC | 27 ms | 1176 KB |
loop/case_032.txt | AC | 28 ms | 1160 KB |
loop/case_033.txt | AC | 29 ms | 1236 KB |
loop/loop_case_000.txt | AC | 28 ms | 1164 KB |
loop/loop_case_001.txt | AC | 29 ms | 1176 KB |
loop/loop_case_002.txt | AC | 29 ms | 1180 KB |
loop/loop_case_003.txt | AC | 27 ms | 1160 KB |
loop/loop_case_004.txt | AC | 28 ms | 1176 KB |
loop/loop_case_005.txt | AC | 27 ms | 1148 KB |
loop/loop_case_006.txt | AC | 28 ms | 1180 KB |
loop/loop_case_007.txt | AC | 28 ms | 1172 KB |
loop/loop_case_008.txt | AC | 28 ms | 1176 KB |
loop/loop_case_009.txt | AC | 28 ms | 1160 KB |
loop/loop_case_010.txt | AC | 28 ms | 1176 KB |
loop/loop_case_011.txt | AC | 28 ms | 1160 KB |
loop/loop_case_012.txt | AC | 29 ms | 1160 KB |
loop/loop_case_013.txt | AC | 28 ms | 1164 KB |
loop/loop_case_014.txt | AC | 28 ms | 1176 KB |
loop/loop_case_015.txt | AC | 30 ms | 1176 KB |
loop/loop_case_016.txt | AC | 29 ms | 1160 KB |
loop/loop_case_017.txt | AC | 26 ms | 1172 KB |
loop/loop_case_018.txt | AC | 30 ms | 1176 KB |
loop/loop_case_019.txt | AC | 29 ms | 1128 KB |
loop/loop_case_020.txt | AC | 28 ms | 1160 KB |
loop/loop_case_021.txt | AC | 29 ms | 1092 KB |
loop/loop_case_022.txt | AC | 30 ms | 1232 KB |
loop/loop_case_023.txt | AC | 29 ms | 1288 KB |
loop/loop_case_024.txt | AC | 30 ms | 1224 KB |
loop/loop_case_025.txt | AC | 30 ms | 1236 KB |
loop/loop_case_026.txt | AC | 30 ms | 1132 KB |
loop/loop_case_027.txt | AC | 29 ms | 1164 KB |
loop/loop_case_028.txt | AC | 28 ms | 1236 KB |
loop/loop_case_029.txt | AC | 29 ms | 1152 KB |
loop/loop_case_030.txt | AC | 28 ms | 1164 KB |
loop/loop_case_031.txt | AC | 28 ms | 1164 KB |
nonloop/case_000.txt | AC | 28 ms | 1176 KB |
nonloop/case_001.txt | AC | 28 ms | 1168 KB |
nonloop/case_002.txt | AC | 28 ms | 1176 KB |
nonloop/case_003.txt | AC | 27 ms | 1172 KB |
nonloop/case_004.txt | AC | 26 ms | 1168 KB |
nonloop/case_005.txt | AC | 30 ms | 1160 KB |
nonloop/case_006.txt | AC | 31 ms | 1172 KB |
nonloop/case_007.txt | AC | 28 ms | 1160 KB |
nonloop/case_008.txt | AC | 29 ms | 1176 KB |
nonloop/case_009.txt | AC | 28 ms | 1172 KB |
nonloop/case_010.txt | AC | 30 ms | 1228 KB |
nonloop/case_011.txt | AC | 29 ms | 1180 KB |
nonloop/case_012.txt | AC | 28 ms | 1164 KB |
nonloop/case_013.txt | AC | 27 ms | 1176 KB |
nonloop/case_014.txt | AC | 29 ms | 1136 KB |
nonloop/case_015.txt | AC | 29 ms | 1260 KB |
nonloop/case_016.txt | AC | 28 ms | 1160 KB |
nonloop/case_017.txt | AC | 27 ms | 1164 KB |
nonloop/case_018.txt | AC | 29 ms | 1180 KB |
nonloop/case_019.txt | AC | 28 ms | 1176 KB |
nonloop/case_020.txt | AC | 29 ms | 1164 KB |
nonloop/case_021.txt | AC | 28 ms | 1160 KB |
nonloop/case_022.txt | AC | 29 ms | 1176 KB |
nonloop/case_023.txt | AC | 29 ms | 1172 KB |
nonloop/case_024.txt | AC | 26 ms | 1168 KB |
nonloop/case_025.txt | AC | 29 ms | 1256 KB |
nonloop/case_026.txt | AC | 29 ms | 1144 KB |
nonloop/case_027.txt | AC | 28 ms | 1164 KB |
nonloop/case_028.txt | AC | 28 ms | 1152 KB |
nonloop/case_029.txt | AC | 29 ms | 1160 KB |
nonloop/case_030.txt | AC | 34 ms | 1168 KB |
nonloop/case_031.txt | AC | 29 ms | 1176 KB |
nonloop/case_032.txt | AC | 29 ms | 1232 KB |
nonloop/case_033.txt | AC | 29 ms | 1164 KB |