結果

問題 No.1083 余りの余り
ユーザー NoneNone
提出日時 2021-02-25 13:56:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,770 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,068 KB
実行使用メモリ 332,900 KB
最終ジャッジ日時 2024-09-25 12:05:24
合計ジャッジ時間 8,344 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,588 KB
testcase_01 AC 42 ms
58,120 KB
testcase_02 AC 60 ms
65,280 KB
testcase_03 AC 44 ms
59,392 KB
testcase_04 AC 62 ms
67,968 KB
testcase_05 AC 2,405 ms
193,380 KB
testcase_06 AC 38 ms
52,480 KB
testcase_07 AC 63 ms
68,224 KB
testcase_08 AC 55 ms
65,664 KB
testcase_09 AC 51 ms
63,360 KB
testcase_10 AC 56 ms
65,280 KB
testcase_11 AC 62 ms
68,224 KB
testcase_12 AC 52 ms
63,616 KB
testcase_13 AC 52 ms
63,872 KB
testcase_14 AC 39 ms
53,120 KB
testcase_15 AC 39 ms
52,864 KB
testcase_16 AC 40 ms
53,120 KB
testcase_17 AC 39 ms
53,120 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