結果
問題 | No.1083 余りの余り |
ユーザー |
|
提出日時 | 2021-02-25 13:46:55 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,770 bytes |
コンパイル時間 | 174 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 331,520 KB |
最終ジャッジ日時 | 2024-09-25 11:59:16 |
合計ジャッジ時間 | 8,955 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 TLE * 1 -- * 15 |
ソースコード
class TravelingSalesman:def __init__(self, N, INF=float("inf"), directed=False, decrement=True):self.N=Nself.directed=directedself.idx=decrementself.INF=INFself.cost = [[INF]*N for _ in range(N)]def add_edge(self,u,v,cost):u,v = u-self.idx, v-self.idxself.cost[u][v] = costif self.directed==False:self.cost[v][u] = costdef shortest(self,start=None):N,INF=self.N,self.INFif start==None: start=self.idxstart=start-self.idxdp = [[INF]*N for _ in range((1<<N))]dp[0][start] = 0for 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)-1if dp[mask][start] == INF:return -1else:return dp[(1<<N)-1][start]def shortest_with_goal(self,start=None,goal=None):""" 始点に戻らない """N,INF=self.N,self.INFif start==None: start=self.idxif goal==None: goal=self.idxstart,goal=start-self.idx,goal-self.idxdp = [[INF]*N for _ in range((1<<N))]dp[1<<start][start] = 0for 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)-1if dp[mask][goal] == INF:return -1else:return dp[(1<<N)-1][goal]def shortest_without_return(self):""" 始点と終点を自由に選んだ時の経路(始点に戻らない)のうち最小の物 """NN,INF=self.N+1,self.INFstart = self.N #extended vertexdp = [[0]*NN for _ in range((1<<NN))]dp[0][start] = Kfor bit in range(1<<NN):for v in range(NN):if not (1<<v)&bit:for u in range(NN):if dp[bit|(1<<v)][v]<dp[bit][u]%A[v] and dp[bit][u]!=0:dp[bit|(1<<v)][v]=dp[bit][u]%A[v]return dp[(1<<NN)-1][start]def draw(self):""":return: グラフを可視化"""import matplotlib.pyplot as pltimport networkx as nxif 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 inputexample = iter("""4 41 2 11 3 32 4 43 4 6""".strip().split("\n"))input = lambda: next(example)########################################################################import sysinput = 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())