結果

問題 No.1690 Power Grid
ユーザー planesplanes
提出日時 2021-09-24 23:47:09
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,988 bytes
コンパイル時間 2,050 ms
コンパイル使用メモリ 181,612 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-18 22:28:56
合計ジャッジ時間 6,385 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h> 
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 #define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

ll INF=1e16;

struct edge{ll to,cost;};
typedef pair<ll,ll> P;
ll V;/*長点数*/
vector<vector<edge>> G;// 各頂点から行けるところを記録
vector<ll> d;// d[i]=sからdへの最短距離

void dijkstra(ll s) {
    priority_queue<P,vector<P>,greater<P>> que;
   d=vector<ll> (V,INF);

    d[s]=0;
    que.push(P(0,s));

    while(!que.empty()) {
        P p=que.top();
        que.pop();
        ll v=p.second;
        if(d[v]<p.first) {
            continue;
        }
        for(ll i=0;i<G[v].size();i++) {
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost) {
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}


ll N,M,K;
vector<vector<ll>> memo;
vector<vector<ll>> r;
vector<ll> A;

ll dp(ll i,ll S) {
    if(memo[i][S]>=0) return memo[i][S];

    ll s=A[i];
    ll cou=0;
    ll kyo=0;

    for(ll j=0;j<N;j++) {
        if(S&(1<<j)){
             cou++;
             if(kyo==0) kyo=r[i][j];
            else  kyo=min(r[i][j],kyo);
    }
    }

    s+=kyo;
    if(cou==K-1) {
        memo[i][S]=s;
    return s;
    }



S|=(1<<i);

ll t=INF;

  for(ll j=0;j<N;j++) {
if(!(S&(1<<j))) {
    t=min(t,dp(j,S));
}
      }
  

  memo[i][S]=s+t;
  
  return s+t;
}



int main() {
cin>>N>>M>>K;
V=N;
A=vector<ll> (N);
for(ll i=0;i<N;i++) cin>>A[i];

G=vector<vector<edge>> (N,vector<edge> (0));
for(ll i=0;i<M;i++) {
    ll X,Y,Z;cin>>X>>Y>>Z;
    X--;Y--;
    edge e={Y,Z};
    edge g={X,Z};
    G[X].push_back(e);
    G[Y].push_back(g);
}

r=vector<vector<ll>> (N,vector<ll> (N));
for(ll i=0;i<N;i++) {
    dijkstra(i);
    for(ll j=0;j<N;j++) {
        r[i][j]=d[j];
    }
}

memo=vector<vector<ll>> (N,vector<ll> ((1<<N),-1));

ll ans=INF;
for(ll i=0;i<N;i++) {
    ans=min(ans,dp(i,0));
}


cout<<ans<<endl;
}
0