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
Task C - 高橋君と国家
User raven38
Language C++ (G++ 4.6.4)
Score 10
Code Size 1849 Byte
Status
Exec Time 130 ms
Memory 932 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0-sample-01.txt, subtask0-sample-02.txt, subtask0-sample-03.txt
Subtask1 10 / 10 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 0 / 20 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 0 / 30 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 0 / 40 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 35 ms 928 KB
subtask0-sample-02.txt 23 ms 932 KB
subtask0-sample-03.txt 27 ms 924 KB
subtask1-01.txt 25 ms 800 KB
subtask1-02.txt 26 ms 928 KB
subtask1-03.txt 30 ms 768 KB
subtask1-04.txt 28 ms 796 KB
subtask1-05.txt 26 ms 800 KB
subtask1-06.txt 26 ms 804 KB
subtask1-07.txt 26 ms 744 KB
subtask1-08.txt 26 ms 808 KB
subtask1-09.txt 35 ms 796 KB
subtask1-10.txt 46 ms 924 KB
subtask1-11.txt 54 ms 748 KB
subtask1-12.txt 48 ms 920 KB
subtask1-13.txt 26 ms 800 KB
subtask1-14.txt 28 ms 800 KB
subtask1-15.txt 29 ms 924 KB
subtask1-16.txt 69 ms 924 KB
subtask1-17.txt 68 ms 928 KB
subtask1-18.txt 26 ms 928 KB
subtask1-19.txt 49 ms 928 KB
subtask1-20.txt 118 ms 800 KB
subtask1-21.txt 115 ms 796 KB
subtask1-22.txt 116 ms 928 KB
subtask1-23.txt 121 ms 924 KB
subtask1-24.txt 120 ms 928 KB
subtask1-25.txt 115 ms 796 KB
subtask1-26.txt 120 ms 800 KB
subtask1-27.txt 121 ms 796 KB
subtask1-28.txt 118 ms 928 KB
subtask1-29.txt 130 ms 804 KB
subtask1-30.txt 122 ms 796 KB
subtask2-01.txt 27 ms 924 KB
subtask2-02.txt 25 ms 800 KB
subtask2-03.txt 26 ms 796 KB
subtask2-04.txt 27 ms 676 KB
subtask2-05.txt 25 ms 796 KB
subtask2-06.txt 27 ms 676 KB
subtask2-07.txt 25 ms 808 KB
subtask2-08.txt 25 ms 808 KB
subtask2-09.txt 25 ms 796 KB
subtask2-10.txt 25 ms 676 KB
subtask2-11.txt 26 ms 800 KB
subtask2-12.txt 27 ms 700 KB
subtask2-13.txt 26 ms 800 KB
subtask2-14.txt 26 ms 800 KB
subtask2-15.txt 25 ms 800 KB
subtask2-16.txt 25 ms 800 KB
subtask2-17.txt 25 ms 796 KB
subtask2-18.txt 27 ms 672 KB
subtask2-19.txt 25 ms 800 KB
subtask2-20.txt 26 ms 792 KB
subtask2-21.txt 25 ms 800 KB
subtask2-22.txt 25 ms 800 KB
subtask2-23.txt 24 ms 736 KB
subtask2-24.txt 25 ms 796 KB
subtask2-25.txt 25 ms 672 KB
subtask2-26.txt 25 ms 800 KB
subtask2-27.txt 25 ms 796 KB
subtask2-28.txt 24 ms 924 KB
subtask2-29.txt 25 ms 800 KB
subtask2-30.txt 26 ms 700 KB
subtask3-01.txt 25 ms 796 KB
subtask3-02.txt 25 ms 796 KB
subtask3-03.txt 26 ms 924 KB
subtask3-04.txt 25 ms 924 KB
subtask3-05.txt 27 ms 732 KB
subtask3-06.txt 26 ms 800 KB
subtask3-07.txt 24 ms 800 KB
subtask3-08.txt 26 ms 796 KB
subtask3-09.txt 25 ms 796 KB
subtask3-10.txt 25 ms 800 KB
subtask3-11.txt 26 ms 804 KB
subtask3-12.txt 26 ms 800 KB
subtask3-13.txt 23 ms 676 KB
subtask3-14.txt 25 ms 800 KB
subtask3-15.txt 24 ms 672 KB
subtask3-16.txt 27 ms 796 KB
subtask3-17.txt 25 ms 796 KB
subtask3-18.txt 25 ms 796 KB
subtask3-19.txt 24 ms 800 KB
subtask3-20.txt 26 ms 924 KB
subtask3-21.txt 25 ms 796 KB
subtask3-22.txt 26 ms 808 KB
subtask3-23.txt 27 ms 676 KB
subtask3-24.txt 26 ms 804 KB
subtask3-25.txt 25 ms 796 KB
subtask3-26.txt 26 ms 804 KB
subtask3-27.txt 27 ms 796 KB
subtask3-28.txt 26 ms 800 KB
subtask3-29.txt 24 ms 804 KB
subtask3-30.txt 26 ms 804 KB
subtask4-01.txt 25 ms 796 KB
subtask4-02.txt 24 ms 796 KB
subtask4-03.txt 26 ms 800 KB
subtask4-04.txt 26 ms 796 KB
subtask4-05.txt 25 ms 796 KB
subtask4-06.txt 27 ms 800 KB
subtask4-07.txt 25 ms 800 KB
subtask4-08.txt 26 ms 920 KB
subtask4-09.txt 26 ms 736 KB
subtask4-10.txt 24 ms 804 KB
subtask4-11.txt 27 ms 800 KB
subtask4-12.txt 30 ms 788 KB
subtask4-13.txt 27 ms 800 KB
subtask4-14.txt 27 ms 796 KB
subtask4-15.txt 25 ms 796 KB
subtask4-16.txt 26 ms 796 KB
subtask4-17.txt 26 ms 804 KB
subtask4-18.txt 27 ms 792 KB
subtask4-19.txt 28 ms 800 KB
subtask4-20.txt 27 ms 792 KB
subtask4-21.txt 26 ms 796 KB
subtask4-22.txt 26 ms 804 KB
subtask4-23.txt 26 ms 672 KB
subtask4-24.txt 26 ms 796 KB
subtask4-25.txt 26 ms 672 KB
subtask4-26.txt 27 ms 804 KB
subtask4-27.txt 26 ms 672 KB
subtask4-28.txt 24 ms 792 KB
subtask4-29.txt 27 ms 800 KB
subtask4-30.txt 26 ms 796 KB