結果

問題 No.95 Alice and Graph
ユーザー ytftytft
提出日時 2022-11-11 02:42:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,577 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 87,040 KB
実行使用メモリ 174,920 KB
最終ジャッジ日時 2023-10-09 22:18:13
合計ジャッジ時間 17,887 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 121 ms
77,960 KB
testcase_04 AC 3,081 ms
171,120 KB
testcase_05 AC 2,927 ms
174,920 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 130 ms
77,840 KB
testcase_09 AC 65 ms
71,132 KB
testcase_10 AC 79 ms
75,948 KB
testcase_11 AC 372 ms
80,944 KB
testcase_12 AC 236 ms
78,744 KB
testcase_13 AC 464 ms
89,508 KB
権限があれば一括ダウンロードができます

ソースコード

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:
		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<<N):
		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