結果

問題 No.1690 Power Grid
ユーザー merlinmerlin
提出日時 2021-09-24 22:43:06
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 48 ms
50,108 KB
testcase_01 AC 46 ms
50,332 KB
testcase_02 AC 49 ms
49,788 KB
testcase_03 AC 46 ms
49,960 KB
testcase_04 AC 45 ms
50,048 KB
testcase_05 AC 45 ms
50,288 KB
testcase_06 AC 236 ms
54,128 KB
testcase_07 AC 241 ms
54,192 KB
testcase_08 AC 247 ms
53,760 KB
testcase_09 AC 246 ms
53,972 KB
testcase_10 AC 232 ms
53,656 KB
testcase_11 AC 284 ms
53,772 KB
testcase_12 AC 47 ms
50,048 KB
testcase_13 AC 48 ms
50,088 KB
testcase_14 AC 131 ms
53,852 KB
testcase_15 AC 259 ms
54,100 KB
testcase_16 AC 233 ms
53,728 KB
testcase_17 AC 149 ms
51,952 KB
testcase_18 AC 147 ms
54,820 KB
testcase_19 AC 220 ms
53,580 KB
testcase_20 AC 247 ms
53,784 KB
testcase_21 AC 291 ms
57,304 KB
testcase_22 AC 245 ms
53,848 KB
testcase_23 AC 235 ms
53,608 KB
testcase_24 AC 283 ms
53,744 KB
testcase_25 AC 246 ms
54,500 KB
testcase_26 AC 232 ms
53,616 KB
testcase_27 AC 46 ms
50,016 KB
権限があれば一括ダウンロードができます

ソースコード

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