結果

問題 No.1690 Power Grid
コンテスト
ユーザー planes
提出日時 2021-09-24 23:47:09
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,988 bytes
コンパイル時間 1,810 ms
コンパイル使用メモリ 184,928 KB
実行使用メモリ 49,308 KB
最終ジャッジ日時 2024-07-05 11:38:25
合計ジャッジ時間 6,285 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

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