結果

問題 No.1690 Power Grid
ユーザー merlinmerlin
提出日時 2021-09-24 22:43:06
言語 Java21
(openjdk 21)
結果
AC  
実行時間 270 ms / 3,000 ms
コード長 1,773 bytes
コンパイル時間 2,253 ms
コンパイル使用メモリ 74,020 KB
実行使用メモリ 55,636 KB
最終ジャッジ日時 2023-09-18 21:51:40
合計ジャッジ時間 8,414 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
49,184 KB
testcase_01 AC 43 ms
49,060 KB
testcase_02 AC 45 ms
49,060 KB
testcase_03 AC 42 ms
49,484 KB
testcase_04 AC 43 ms
49,160 KB
testcase_05 AC 43 ms
49,396 KB
testcase_06 AC 265 ms
53,824 KB
testcase_07 AC 259 ms
54,480 KB
testcase_08 AC 260 ms
54,176 KB
testcase_09 AC 261 ms
53,904 KB
testcase_10 AC 260 ms
53,820 KB
testcase_11 AC 260 ms
53,760 KB
testcase_12 AC 44 ms
49,104 KB
testcase_13 AC 47 ms
49,272 KB
testcase_14 AC 92 ms
51,652 KB
testcase_15 AC 258 ms
54,608 KB
testcase_16 AC 262 ms
54,032 KB
testcase_17 AC 159 ms
51,928 KB
testcase_18 AC 118 ms
51,880 KB
testcase_19 AC 253 ms
53,944 KB
testcase_20 AC 254 ms
53,376 KB
testcase_21 AC 264 ms
54,016 KB
testcase_22 AC 270 ms
54,332 KB
testcase_23 AC 251 ms
55,636 KB
testcase_24 AC 260 ms
53,492 KB
testcase_25 AC 268 ms
54,308 KB
testcase_26 AC 266 ms
53,936 KB
testcase_27 AC 43 ms
49,116 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