結果

問題 No.1083 余りの余り
ユーザー NoneNone
提出日時 2021-02-25 13:56:10
言語 PyPy3
(7.3.13)
結果
TLE  
実行時間 -
コード長 3,770 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 81,680 KB
実行使用メモリ 329,848 KB
最終ジャッジ日時 2023-10-26 04:18:09
合計ジャッジ時間 8,847 ms
ジャッジサーバーID
(参考情報)
judge13 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,532 KB
testcase_01 AC 43 ms
58,984 KB
testcase_02 AC 58 ms
66,260 KB
testcase_03 AC 44 ms
59,664 KB
testcase_04 AC 69 ms
68,400 KB
testcase_05 AC 2,484 ms
193,252 KB
testcase_06 AC 40 ms
53,532 KB
testcase_07 AC 64 ms
68,336 KB
testcase_08 AC 57 ms
66,260 KB
testcase_09 AC 55 ms
64,208 KB
testcase_10 AC 58 ms
66,260 KB
testcase_11 AC 64 ms
68,336 KB
testcase_12 AC 55 ms
64,208 KB
testcase_13 AC 54 ms
64,208 KB
testcase_14 AC 40 ms
53,532 KB
testcase_15 AC 41 ms
53,532 KB
testcase_16 AC 40 ms
53,532 KB
testcase_17 AC 42 ms
53,532 KB
testcase_18 TLE -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

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(self,start=None):
        N,INF=self.N,self.INF

        if start==None: start=self.idx
        start=start-self.idx
        dp = [[INF]*N for _ in range((1<<N))]
        dp[0][start] = 0
        for bit in range(1<<N):
            for v in range(N):
                if not (1<<v)&bit:
                    for u in range(N):
                        if dp[bit|(1<<v)][v]>dp[bit][u]+self.cost[u][v] and dp[bit][u]!=INF:
                            dp[bit|(1<<v)][v]=dp[bit][u]+self.cost[u][v]

        mask=(1<<N)-1
        if dp[mask][start] == INF:
            return -1
        else:
            return dp[(1<<N)-1][start]

    def shortest_with_goal(self,start=None,goal=None):
        """ 始点に戻らない """
        N,INF=self.N,self.INF

        if start==None: start=self.idx
        if goal==None: goal=self.idx
        start,goal=start-self.idx,goal-self.idx
        dp = [[INF]*N for _ in range((1<<N))]
        dp[1<<start][start] = 0
        for bit in range(1<<N):
            for v in range(N):
                if not (1<<v)&bit:
                    for u in range(N):
                        if dp[bit|(1<<v)][v]>dp[bit][u]+self.cost[u][v] and dp[bit][u]!=INF:
                            dp[bit|(1<<v)][v]=dp[bit][u]+self.cost[u][v]

        mask=(1<<N)-1
        if dp[mask][goal] == INF:
            return -1
        else:
            return dp[(1<<N)-1][goal]

    def shortest_without_return(self):
        """ 始点と終点を自由に選んだ時の経路(始点に戻らない)のうち最小の物 """
        NN,INF=self.N+1,self.INF
        start = self.N      #extended vertex

        dp = [[0]*NN for _ in range((1<<NN))]
        dp[0][start] = K
        for bit in range(1<<NN):
            for v in range(NN):
                if not (1<<v)&bit:
                    for u in range(NN):
                        if dp[bit][u]!=0 and dp[bit|(1<<v)][v]<dp[bit][u]%A[v]:
                            dp[bit|(1<<v)][v]=dp[bit][u]%A[v]

        return dp[(1<<NN)-1][start]

    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)



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

# example()

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

print(ts.shortest_without_return())
0