結果

問題 No.1083 余りの余り
ユーザー None
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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|(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 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())
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0