結果

問題 No.1690 Power Grid
コンテスト
ユーザー merlin
提出日時 2021-09-24 22:43:06
言語 Java
(openjdk 23)
結果
AC  
実行時間 291 ms / 3,000 ms
コード長 1,773 bytes
コンパイル時間 1,742 ms
コンパイル使用メモリ 78,120 KB
実行使用メモリ 57,304 KB
最終ジャッジ日時 2024-07-05 11:02:53
合計ジャッジ時間 7,387 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        String s[]=bu.readLine().split(" ");
        int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]),l=Integer.parseInt(s[2]);
        long g[][]=new long[n][n],M=(long)1e18;
        int i,j,k;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++) g[i][j]=M;

        int a[]=new int[n];
        s=bu.readLine().split(" ");
        for(i=0;i<n;i++)
        {
            a[i]=Integer.parseInt(s[i]);
            g[i][i]=0;
        }

        for(i=0;i<m;i++)
        {
            s=bu.readLine().split(" ");
            int u=Integer.parseInt(s[0]),v=Integer.parseInt(s[1]),w=Integer.parseInt(s[2]);
            u--; v--;
            g[u][v]=Math.min(g[u][v],w);
            g[v][u]=Math.min(g[v][u],w);
        }

        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        for(k=0;k<n;k++) g[j][k]=Math.min(g[j][k],g[j][i]+g[i][k]);

        int mx=1<<n;
        long dp[]=new long[mx];
        Arrays.fill(dp,M);
        dp[0]=0;
        for(i=0;i<n;i++) dp[1<<i]=a[i];

        for(i=1;i<mx;i++)
        {
            for(j=0;j<n;j++)
            if(((i>>j)&1)==0)
            {
                long min=M;
                for(k=0;k<n;k++)
                if(((i>>k)&1)==1) min=Math.min(min,g[j][k]);
                dp[i|(1<<j)]=Math.min(dp[i|1<<j],dp[i]+min+a[j]);
            }
        }

        long ans=M;
        for(i=0;i<mx;i++)
        {
            k=0;
            for(j=0;j<n;j++)
            if(((i>>j)&1)==1) k++;
            if(k==l) ans=Math.min(ans,dp[i]);
        }
        System.out.println(ans);
    }
}
0