Contest Duration: ~ (local time) (90 minutes) Back to Home

Submission #241889

Source Code Expand

Copy
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <climits>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF (LLONG_MAX/2)
#define EPS 1e-10

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

ll N, M;
ll c[100002], a[20000], b[20000], r[20000];
ll G[10000][10000];
int f[100];

void rec(int n){
rep(i, N){
if(!G[n][i] || f[i]) continue;
f[i] = 1;
rec(i);
}
}

int ok(){
memset(f, 0, sizeof(f));

rep(i, N){
if(!G[i][i]) continue;
f[i] = 1;
rec(i);
}

rep(i, N) if(!f[i]) return 0;
//  puts("ok");
return 1;
}

ll dfs(ll n){
if(n == N+M){
if(ok()) return 0;
return INF;
}
ll res = INF;

if(n < N){
res = min(res, dfs(n+1));
G[n][n] = 1;
res = min(res, dfs(n+1)+c[n]);
G[n][n] = 0;
}else{
int nn = n-N;
res = min(res, dfs(n+1));
G[a[nn]][b[nn]] = G[b[nn]][a[nn]] = 1;
res = min(res, dfs(n+1)+r[nn]);
G[a[nn]][b[nn]] = G[b[nn]][a[nn]] = 0;
}
//  cout << res << endl;
return res;
}

int main(){
cin >> N >> M;
if(N > 8 || M > 10) return 0;
rep(i, N) cin >> c[i];
rep(i, M){
cin >> a[i] >> b[i] >> r[i];
a[i]--; b[i]--;
}

printf("%lld\n", dfs(0));
return 0;
}
```

#### Submission Info

Submission Time 2014-09-27 21:57:25+0900 C - 高橋君と国家 raven38 C++ (G++ 4.6.4) 10 1849 Byte WA 130 ms 932 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Case Name Status Exec Time Memory