結果

問題 No.1690 Power Grid
ユーザー NoneNone
提出日時 2021-10-05 14:56:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 907 ms / 3,000 ms
コード長 6,334 bytes
コンパイル時間 163 ms
コンパイル使用メモリ 82,280 KB
実行使用メモリ 78,592 KB
最終ジャッジ日時 2024-07-23 02:34:47
合計ジャッジ時間 14,413 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
53,120 KB
testcase_01 AC 44 ms
53,248 KB
testcase_02 AC 64 ms
68,352 KB
testcase_03 AC 40 ms
53,120 KB
testcase_04 AC 41 ms
53,120 KB
testcase_05 AC 41 ms
53,376 KB
testcase_06 AC 675 ms
78,112 KB
testcase_07 AC 669 ms
77,952 KB
testcase_08 AC 678 ms
78,208 KB
testcase_09 AC 677 ms
78,384 KB
testcase_10 AC 891 ms
78,080 KB
testcase_11 AC 670 ms
77,992 KB
testcase_12 AC 41 ms
53,248 KB
testcase_13 AC 64 ms
68,736 KB
testcase_14 AC 155 ms
76,416 KB
testcase_15 AC 675 ms
78,136 KB
testcase_16 AC 684 ms
77,952 KB
testcase_17 AC 348 ms
76,544 KB
testcase_18 AC 254 ms
77,024 KB
testcase_19 AC 907 ms
78,592 KB
testcase_20 AC 672 ms
78,020 KB
testcase_21 AC 675 ms
77,824 KB
testcase_22 AC 904 ms
78,012 KB
testcase_23 AC 897 ms
78,308 KB
testcase_24 AC 896 ms
77,952 KB
testcase_25 AC 677 ms
78,296 KB
testcase_26 AC 689 ms
78,080 KB
testcase_27 AC 41 ms
53,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def popcnt(n):
    """ n<=64 """
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

def k_bits(n,k):
    """ subset with popcnt = k in (1<<n)-1  ( O(nCk) )"""
    comb=(1<<k)-1
    while comb<(1<<n):
        yield comb
        x=comb&-comb
        y=comb+x
        comb=((comb&~y)//x>>1)|y

def bit_rep(bit,N):
    return format(bit, "0" + str(N) + "b")

class TravelingSalesman:

    def __init__(self, N, INF=float("inf"), directed=False, decrement=True):
        self.N=N
        self.directed=directed
        self.idx=decrement
        self.INF=INF
        self.cost = [[INF]*N for _ in range(N)]

    def add_edge(self,u,v,cost):
        u,v = u-self.idx, v-self.idx
        self.cost[u][v] = cost
        if self.directed==False:
            self.cost[v][u] = cost



    def shortest_without_return(self):
        """ 始点と終点を自由に選んだ時の経路（始点に戻らない）のうち最小の物 """
        N,INF=self.N,self.INF
        cost = [[INF]*N for _ in range(N)]
        for u in range(N):
            for v in range(N):
                cost[u][v]=self.cost[u][v]

        dp = [INF]*(1<<N)
        for v in range(N):
            dp[1<<v]=A[v]
        for bit in range(1<<N):
            for v in range(N):
                if not (1<<v)&bit:
                    for u in range(N):
                        if not (1<<u)&bit or u==v:
                            continue
                        if dp[bit|(1<<v)]>dp[bit]+cost[u][v]+A[v] and dp[bit]!=INF:
                            dp[bit|(1<<v)]=dp[bit]+cost[u][v]+A[v]
                            # print(bit_rep(bit|(1<<v),N),v,dp[bit|(1<<v)],A[v])

        res=INF
        for bit in k_bits(N,K):
            # print(bit_rep(bit,N),dp[bit])
            res=min(dp[bit],res)
        return res

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.directed==True:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x in range(self.N):
            for y in range(self.N):
                if self.cost[x][y]!=self.INF:
                    G.add_edge(x + self.idx, y + self.idx, weight=self.cost[x][y])

        edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos, with_labels=True, connectionstyle='arc3, rad = 0.1')
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.axis("off")
        plt.show()

########################################################################

def example():
    global input
    example = iter(
        """
4 4
1 2 1
1 3 3
2 4 4
3 4 6
        """
            .strip().split("\n"))
    input = lambda: next(example)

class Graph:
    def __init__(self, n, directed=False, decrement=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.edges2 = []                            # ワーシャルフロイド用
        self.dist = [INF]*(n*n)
        for i in range(self.n):
            self.dist[i*n+i] = 0  # 自身のところに行くコストは０
        for x, y, cost in edges:
            self.add_edge(x, y, cost)

    def add_edge(self, x, y, cost):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges2.append((x, y, cost))
        if self.directed == False:
            self.edges2.append((y, x, cost))

    def warshall_folyd(self):
        """
        :param INF: INF = 10**18 にすると、負のコストがある場合に少し面倒になる
        :return: 頂点 i, j 間の距離を行列として返す (0-indexed)
        """

        dist=self.dist
        n=self.n

        for i, j, cost in self.edges2:
            dist[i*n+j] = cost

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i*n+j] > dist[i*n+k] + dist[k*n+j]:
                        dist[i*n+j] = dist[i*n+k] + dist[k*n+j]
        return dist

    def update(self, x, y, cost):
        dist=self.dist
        n=self.n
        if self.decrement:
            x -= 1
            y -= 1
        flg=0
        if dist[x*n+y]>cost:
            dist[x*n+y]=cost
            flg=1
        if not self.directed:
            if dist[y*n+x]>cost:
                dist[y*n+x]=cost
                flg=1
        if flg==0:
            return dist
        for i in range(self.n):
            for j in range(self.n):
                dist[i*n+j] = min(dist[i*n+j],dist[i*n+x]+cost+dist[y*n+j])
                if not self.directed:
                    dist[i*n+j]=min(dist[i*n+j],dist[i*n+y]+cost+dist[x*n+j])

        return dist

    def draw(self):
        """
        :return: グラフを可視化
        """
        import matplotlib.pyplot as plt
        import networkx as nx

        if self.directed:
            G = nx.DiGraph()
        else:
            G = nx.Graph()
        for x, y, cost in self.edges2:
            G.add_edge(x + self.decrement, y + self.decrement, weight=cost)

        edge_labels = {(i, j): w['weight'] for i, j, w in G.edges(data=True)}
        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos, with_labels=True)
        nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
        plt.axis("off")
        plt.show()

########################################################################
import sys
input = sys.stdin.readline

# example()

INF=10**18
N, M, K = map(int, input().split())
ts=TravelingSalesman(N,INF=INF,directed=False,decrement=False)
A=list(map(int, input().split()))

graph = Graph(N, directed=False, decrement=False)
for _ in range(M):
    u,v,cost=map(int, input().split())
    u-=1
    v-=1
    graph.add_edge(u, v, cost)
dist=graph.warshall_folyd()
for u in range(N):
    for v in range(N):
        ts.add_edge(u,v,dist[u*N+v])
print(ts.shortest_without_return())
0