結果
問題 | No.1690 Power Grid |
ユーザー | publfl |
提出日時 | 2021-09-24 22:34:14 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 109 ms / 3,000 ms |
コード長 | 1,792 bytes |
コンパイル時間 | 583 ms |
コンパイル使用メモリ | 60,452 KB |
実行使用メモリ | 89,064 KB |
最終ジャッジ日時 | 2023-09-18 21:48:25 |
合計ジャッジ時間 | 2,897 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
13,220 KB |
testcase_01 | AC | 4 ms
17,336 KB |
testcase_02 | AC | 6 ms
25,568 KB |
testcase_03 | AC | 2 ms
7,060 KB |
testcase_04 | AC | 2 ms
7,132 KB |
testcase_05 | AC | 3 ms
11,204 KB |
testcase_06 | AC | 56 ms
68,584 KB |
testcase_07 | AC | 52 ms
68,588 KB |
testcase_08 | AC | 54 ms
68,564 KB |
testcase_09 | AC | 53 ms
68,548 KB |
testcase_10 | AC | 25 ms
52,132 KB |
testcase_11 | AC | 105 ms
87,028 KB |
testcase_12 | AC | 4 ms
17,376 KB |
testcase_13 | AC | 8 ms
33,780 KB |
testcase_14 | AC | 16 ms
56,308 KB |
testcase_15 | AC | 103 ms
89,064 KB |
testcase_16 | AC | 52 ms
68,572 KB |
testcase_17 | AC | 31 ms
62,396 KB |
testcase_18 | AC | 19 ms
58,340 KB |
testcase_19 | AC | 52 ms
68,544 KB |
testcase_20 | AC | 55 ms
68,600 KB |
testcase_21 | AC | 24 ms
50,156 KB |
testcase_22 | AC | 102 ms
76,784 KB |
testcase_23 | AC | 109 ms
89,056 KB |
testcase_24 | AC | 108 ms
82,892 KB |
testcase_25 | AC | 108 ms
84,968 KB |
testcase_26 | AC | 109 ms
87,008 KB |
testcase_27 | AC | 4 ms
17,336 KB |
ソースコード
#include <stdio.h> #include <vector> #include <queue> #define MAX (long long int)1e16 int a; std::vector< std::pair<int,int> > V[110]; long long int dist[110][110]; std::priority_queue< std::pair<long long int,int> > Q; void init(int target) { for(int i=1;i<=a;i++) dist[target][i] = MAX; Q.push(std::make_pair(0,target)); while(!Q.empty()) { std::pair<long long int,int> A = Q.top(); Q.pop(); A.first *= (-1); if(dist[target][A.second]!=MAX) continue; dist[target][A.second] = A.first; for(int i=0;i<V[A.second].size();i++) { Q.push(std::make_pair(-(A.first+V[A.second][i].second),V[A.second][i].first)); } } } int x[110]; long long int dist2[21][300010]; void init2(int k, int bit, long long int min, int target) { if(k==0) { dist2[target][bit] = min; return; } init2(k-1,bit,min,target); init2(k-1,bit^(1<<(k-1)),min<dist[target][k]?min:dist[target][k],target); } long long int check[21][300010]; long long int func(int k, int bit) { if(k==0) return 0; if(check[k][bit]!=MAX) return check[k][bit]; long long int ans = MAX; for(int i=1;i<=a;i++) { if(((bit>>(i-1))&1)==0) { long long int t = func(k-1,bit+(1<<(i-1))) + dist2[i][bit] + x[i]; ans = ans<t?ans:t; } } return check[k][bit] = ans; } int main() { int b,c; scanf("%d%d%d",&a,&b,&c); for(int i=1;i<=a;i++) scanf("%d",&x[i]); for(int i=1;i<=b;i++) { int d,e,f; scanf("%d%d%d",&d,&e,&f); V[d].push_back(std::make_pair(e,f)); V[e].push_back(std::make_pair(d,f)); } for(int i=1;i<=a;i++) init(i); for(int i=1;i<=a;i++) init2(a,0,MAX,i); for(int i=1;i<=c;i++) for(int j=0;j<(1<<a);j++) check[i][j] = MAX; long long int ans = MAX; for(int i=1;i<=a;i++) { long long int t = func(c-1,1<<(i-1)) + x[i]; ans = ans<t?ans:t; } printf("%lld",ans); }