Submission #241866


Source Code Expand

Copy
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
#include <memory>
#include <time.h>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXIST2(s,e) (find(ALL(s),(e))!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-9;
const double PI  = acos(-1.0);

typedef vector<ll> vl;
typedef vector<vl> vvl;
const int MAX_V=13;
const ll INF=1LL<<40;

ll cost[MAX_V][MAX_V];
ll mincost[MAX_V];
bool used[MAX_V];
int V;

ll prim(){
	for(int i=0;i<V;i++){
		mincost[i]=INF;
		used[i]=false;
	}

	mincost[0]=0;
	int res=0;

	while(true){
		int v=-1;
		for(int u=0;u<V;u++){
			if(!used[u]&&(v==-1||mincost[u]<mincost[v])) v=u;
		}

		if(v==-1)break;
		used[v]=true;
		res+=mincost[v];
		for(int u=0;u<V;u++){
			mincost[u]=min(mincost[u],cost[v][u]);
		}
	}
	return res;
}

int main(){
	int n,m;
	cin>>n>>m;
	vi c(n);
	REP(i,n){
		cin>>c[i];
	}
	vvl road_costs(n,vl(n,INF));
	REP(i,m){
		int a,b,r;
		cin>>a>>b>>r,a--,b--;
		road_costs[a][b]=r;
		road_costs[b][a]=r;
	}
	ll ans=LLONG_MAX;
	V=n;
	FOR(mask,1,1<<n){
		ll tmp=0;
		REP(i,n){
			if((mask>>i)&1){
				tmp+=c[i];
			}
		}
		REP(i,V){
			REP(j,V){
				if(((mask>>i)&1)&&((mask>>j)&1)){
					cost[i][j]=0;
				}else{
					cost[i][j]=road_costs[i][j];
				}
			}
		}
		tmp+=prim();
		ans=min(ans,tmp);
	}
	cout<<ans<<endl;
}

Submission Info

Submission Time
Task C - 高橋君と国家
User SSJJ
Language C++ (G++ 4.6.4)
Score 0
Code Size 2157 Byte
Status
Exec Time 2181 ms
Memory 1048576 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 0 / 10 0 / 20 0 / 30 0 / 40
Status
× 3
× 20
× 13
× 36
× 27
× 36
× 28
× 29
× 36
× 28
× 28
× 1
× 30
Set Name Test Cases
Sample subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt
Subtask1 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt
Subtask2 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt
Subtask3 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt
Subtask4 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask1-21.txt, subtask1-22.txt, subtask1-23.txt, subtask1-24.txt, subtask1-25.txt, subtask1-26.txt, subtask1-27.txt, subtask1-28.txt, subtask1-29.txt, subtask1-30.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt, subtask2-21.txt, subtask2-22.txt, subtask2-23.txt, subtask2-24.txt, subtask2-25.txt, subtask2-26.txt, subtask2-27.txt, subtask2-28.txt, subtask2-29.txt, subtask2-30.txt, subtask3-01.txt, subtask3-02.txt, subtask3-03.txt, subtask3-04.txt, subtask3-05.txt, subtask3-06.txt, subtask3-07.txt, subtask3-08.txt, subtask3-09.txt, subtask3-10.txt, subtask3-11.txt, subtask3-12.txt, subtask3-13.txt, subtask3-14.txt, subtask3-15.txt, subtask3-16.txt, subtask3-17.txt, subtask3-18.txt, subtask3-19.txt, subtask3-20.txt, subtask3-21.txt, subtask3-22.txt, subtask3-23.txt, subtask3-24.txt, subtask3-25.txt, subtask3-26.txt, subtask3-27.txt, subtask3-28.txt, subtask3-29.txt, subtask3-30.txt, subtask4-01.txt, subtask4-02.txt, subtask4-03.txt, subtask4-04.txt, subtask4-05.txt, subtask4-06.txt, subtask4-07.txt, subtask4-08.txt, subtask4-09.txt, subtask4-10.txt, subtask4-11.txt, subtask4-12.txt, subtask4-13.txt, subtask4-14.txt, subtask4-15.txt, subtask4-16.txt, subtask4-17.txt, subtask4-18.txt, subtask4-19.txt, subtask4-20.txt, subtask4-21.txt, subtask4-22.txt, subtask4-23.txt, subtask4-24.txt, subtask4-25.txt, subtask4-26.txt, subtask4-27.txt, subtask4-28.txt, subtask4-29.txt, subtask4-30.txt
Case Name Status Exec Time Memory
subtask0-sample-01.txt 27 ms 868 KB
subtask0-sample-02.txt 30 ms 796 KB
subtask0-sample-03.txt 31 ms 796 KB
subtask1-01.txt 30 ms 924 KB
subtask1-02.txt 30 ms 876 KB
subtask1-03.txt 31 ms 812 KB
subtask1-04.txt 30 ms 876 KB
subtask1-05.txt 27 ms 920 KB
subtask1-06.txt 29 ms 924 KB
subtask1-07.txt 29 ms 872 KB
subtask1-08.txt 31 ms 796 KB
subtask1-09.txt 30 ms 876 KB
subtask1-10.txt 30 ms 812 KB
subtask1-11.txt 29 ms 868 KB
subtask1-12.txt 29 ms 872 KB
subtask1-13.txt 44 ms 816 KB
subtask1-14.txt 44 ms 812 KB
subtask1-15.txt 53 ms 820 KB
subtask1-16.txt 30 ms 788 KB
subtask1-17.txt 29 ms 860 KB
subtask1-18.txt 29 ms 920 KB
subtask1-19.txt 30 ms 924 KB
subtask1-20.txt 30 ms 796 KB
subtask1-21.txt 30 ms 812 KB
subtask1-22.txt 32 ms 804 KB
subtask1-23.txt 28 ms 876 KB
subtask1-24.txt 28 ms 920 KB
subtask1-25.txt 30 ms 876 KB
subtask1-26.txt 30 ms 876 KB
subtask1-27.txt 30 ms 924 KB
subtask1-28.txt 29 ms 856 KB
subtask1-29.txt 30 ms 876 KB
subtask1-30.txt 30 ms 812 KB
subtask2-01.txt 30 ms 856 KB
subtask2-02.txt 33 ms 856 KB
subtask2-03.txt 30 ms 856 KB
subtask2-04.txt 32 ms 872 KB
subtask2-05.txt 35 ms 796 KB
subtask2-06.txt 33 ms 744 KB
subtask2-07.txt 34 ms 920 KB
subtask2-08.txt 31 ms 868 KB
subtask2-09.txt 34 ms 796 KB
subtask2-10.txt 31 ms 872 KB
subtask2-11.txt 34 ms 872 KB
subtask2-12.txt 34 ms 740 KB
subtask2-13.txt 38 ms 768 KB
subtask2-14.txt 33 ms 872 KB
subtask2-15.txt 41 ms 816 KB
subtask2-16.txt 38 ms 880 KB
subtask2-17.txt 38 ms 852 KB
subtask2-18.txt 39 ms 880 KB
subtask2-19.txt 37 ms 872 KB
subtask2-20.txt 39 ms 868 KB
subtask2-21.txt 39 ms 868 KB
subtask2-22.txt 38 ms 876 KB
subtask2-23.txt 38 ms 796 KB
subtask2-24.txt 38 ms 876 KB
subtask2-25.txt 38 ms 808 KB
subtask2-26.txt 38 ms 792 KB
subtask2-27.txt 38 ms 800 KB
subtask2-28.txt 38 ms 832 KB
subtask2-29.txt 38 ms 860 KB
subtask2-30.txt 39 ms 920 KB
subtask3-01.txt 302 ms 1132 KB
subtask3-02.txt 301 ms 1580 KB
subtask3-03.txt 309 ms 2780 KB
subtask3-04.txt 42 ms 5868 KB
subtask3-05.txt 319 ms 8680 KB
subtask3-06.txt 323 ms 12132 KB
subtask3-07.txt 322 ms 12268 KB
subtask3-08.txt 335 ms 18416 KB
subtask3-09.txt 356 ms 26224 KB
subtask3-10.txt 361 ms 32100 KB
subtask3-11.txt 390 ms 49704 KB
subtask3-12.txt 436 ms 71264 KB
subtask3-13.txt 427 ms 71260 KB
subtask3-14.txt 439 ms 71260 KB
subtask3-15.txt 439 ms 71284 KB
subtask3-16.txt 431 ms 71272 KB
subtask3-17.txt 428 ms 71280 KB
subtask3-18.txt 434 ms 71272 KB
subtask3-19.txt 428 ms 71256 KB
subtask3-20.txt 438 ms 71260 KB
subtask3-21.txt 441 ms 71280 KB
subtask3-22.txt 442 ms 71260 KB
subtask3-23.txt 442 ms 71260 KB
subtask3-24.txt 438 ms 71256 KB
subtask3-25.txt 438 ms 71280 KB
subtask3-26.txt 441 ms 71228 KB
subtask3-27.txt 447 ms 71276 KB
subtask3-28.txt 445 ms 71280 KB
subtask3-29.txt 448 ms 71256 KB
subtask3-30.txt 471 ms 71260 KB
subtask4-01.txt 677 ms 196328 KB
subtask4-02.txt 1905 ms 779908 KB
subtask4-03.txt 2080 ms 1048576 KB
subtask4-04.txt 2094 ms 1048576 KB
subtask4-05.txt 2088 ms 1048576 KB
subtask4-06.txt 2166 ms 878308 KB
subtask4-07.txt 2170 ms 873840 KB
subtask4-08.txt 2181 ms 882088 KB
subtask4-09.txt 2158 ms 884368 KB
subtask4-10.txt 2173 ms 884148 KB
subtask4-11.txt 2167 ms 875448 KB
subtask4-12.txt 2177 ms 872904 KB
subtask4-13.txt 2170 ms 881124 KB
subtask4-14.txt 2181 ms 873188 KB
subtask4-15.txt 2162 ms 869728 KB
subtask4-16.txt 2172 ms 865868 KB
subtask4-17.txt 2162 ms 884572 KB
subtask4-18.txt 2170 ms 886236 KB
subtask4-19.txt 2166 ms 885176 KB
subtask4-20.txt 2168 ms 885052 KB
subtask4-21.txt 2166 ms 886620 KB
subtask4-22.txt 2165 ms 884824 KB
subtask4-23.txt 2164 ms 874820 KB
subtask4-24.txt 2164 ms 886616 KB
subtask4-25.txt 2158 ms 878936 KB
subtask4-26.txt 2162 ms 885084 KB
subtask4-27.txt 2153 ms 882776 KB
subtask4-28.txt 2166 ms 878756 KB
subtask4-29.txt 2167 ms 883924 KB
subtask4-30.txt 2165 ms 885852 KB