結果

問題 No.95 Alice and Graph
コンテスト
ユーザー ytft
提出日時 2022-11-11 08:19:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,583 bytes
コンパイル時間 424 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 508,216 KB
最終ジャッジ日時 2024-09-13 03:22:44
合計ジャッジ時間 17,565 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys,heapq
input=lambda:sys.stdin.readline().rstrip()
class node:
    def __init__(self,con):
        self.con=con
class directedWeightedGraph:
    def __init__(self,N,edges=[]):
        self.N=N
        self.nodes=[node([]) for i in range(N)]
        for i in edges:
            self.nodes[i[0]].append(i[1:])
    def connect(self,f,t,weight=0):
        self.nodes[f].con.append([t,weight])
    def dijkstra(self,start):
        ans=[float('inf') for i in range(self.N)]
        watch=[]
        heapq.heappush(watch, [0,start])
        while watch:
            cur=heapq.heappop(watch)
            if ans[cur[1]]==float('inf'):
                ans[cur[1]]=cur[0]
                for i in self.nodes[cur[1]].con:
                    heapq.heappush(watch,[i[1]+ans[cur[1]],i[0]])
        return ans
def check(d_,val,N_,K):
	N=0
	l=[]
	for i in range(N_):
		if (val>>i)%2:
			N+=1
			l.append(i)
	if N>K+1:
		return 0
	d=[[float('inf') for i in range(N)] for j in range(N)]
	for i in range(N):
		for j in range(N):
			d[i][j]=d_[l[i]][l[j]]
	dp=[[float('inf') for i in range(1<<N)] for j in range(N)]
	dp[0][1]=0
	for i in range(1,1<<N,2):
		for j in range(N):
			for k in range(N):
				dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+d[j][k])
	return min([i[(1<<N)-1] for i in dp])<=K
N,M,K=map(int,input().split())
G=directedWeightedGraph(N)
for i in range(M):
	a,b=map(int,input().split())
	G.connect(a-1,b-1,1)
	G.connect(b-1,a-1,1)
d=[G.dijkstra(i) for i in range(N)]
cur,ans=1,0
for i in range(N-1,0,-1):
	if check(d,cur+(1<<i),N,K):
		ans+=(1<<i)-1
		cur+=(1<<i)
print(ans)
0