square869120Contest #1 G - Revenge of Traveling Salesman Problem

bit dp の問題。dp[ i ][ k ] = (a,b) として、今まで通った頂点を表す bit i と今いる頂点 k が入りその時の最小値 a と最小値をとりうる通り方の総数 b が保管されている。
k から次の頂点 j に行けるのは i の j の位が０であるときで、
かつ、dp[ i ][ k ][ 0 ] + g[ k ][ j ] <= t[ k ][ j ] を満たすときである。
( g[ k ][ j ] は k から j までの距離、道が無ければ inf )
( t[ k ][ j ] は k から j までの道が開いている時間)
また総数の変化は dp[ i ][ k ] から dp [ i + 2**j ][ j ]に行くときに最小値が更新されるなら
dp[ i+2**j ][ j ] = [ dp[ i ][ k ][ 0 ]+g[ k ][ j ], dp[ i ][ k ][ 1 ] ]
dp[ i ][ k ][ 0 ]+g[ k ][ j ] == dp[ i+2**j ][ j ][ 0 ] となるなら
dp[ i+2**j ][ j ][ 1 ] += dp[ i ][ k ][ 1 ] となる。

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
g = [[10**12+1]*n for _ in range(n)]
t = [[0]*n for _ in range(n)]
for _ in range(m):
    a,b,c,d = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c
    t[a][b] = d
    t[b][a] = d
    
dp = [[[10**12+1,0]]*n for i in range(2**n)]
dp[0][0] = [0,1]

for i in range(2**n):
  for j in range(n):
    if i>>j&1 == 0:
      for k in range(n):
        if dp[i][k][0]+g[k][j] <= t[k][j]:
          if dp[i][k][0]+g[k][j] == dp[i+2**j][j][0]:
            dp[i+2**j][j][1] += dp[i][k][1]
          elif dp[i][k][0]+g[k][j] < dp[i+2**j][j][0]:
            dp[i+2**j][j] = [dp[i][k][0]+g[k][j],dp[i][k][1]]
            
if dp[2**n-1][0][0] > 10**12:
  print('IMPOSSIBLE')
else:
  print(*dp[2**n-1][0])