解答：Submission #24919698 - AtCoder Beginner Contest 212
解法：DP。
dp[i][j]：i日目に都市jにいるときの場合の数とする。答えはdp[K][0]である。
Eを使える道の集合とする。
dp[i][j]
= Σdp[i-1][k] ( (k, j) in E)
= Σdp[i-1][k] (all k) - Σdp[i-1][k] ( (k, j) NOT in E)
ここで、「all k」は各j間で使いまわし可能、「(k, j) NOT in E」は問題で与えられる辺の集合で全てのjを計算しても高々5000である。よって最終的な計算量はO(K * (N + M))となり、間に合う。
