Problem:


Problem H: いけるかな？

  

    あるところに，日本各地をまわりながら商売をする社長がいた．
    彼はある日，不思議な切符を手に入れた．
    その切符を使うと，なんと目的地までの距離によらず電車の運賃が無料になるという．
    ただし，
    現在の駅から隣接する駅へ移動するのを1ステップと数えたときに，
    移動するステップ数がちょうど切符に書かれた数と等しくならないと
    追加料金を取られてしまう．
    ある区間をただちに折り返すような移動は禁止されているが，
    既に訪れた駅や区間を複数回通ること自体は許される．
    たとえば，駅1・駅2・駅1と移動することはできないが，
    駅1・駅2・駅3・駅1・駅2のような移動は問題ない．
    また，最終的に目的地に到着するならば，出発地や目的地も何度でも通ってよい．
  

  

    社長はさっそくこの切符を次の目的地に行くために使ってみようと考えた．
    しかし路線図は入り組んでいるため，簡単には経路が定まらない．
    あなたの仕事は，社長に代わって目的地に無料で到達できるかどうかを
    判定するプログラムを書くことである．
  

  

    駅は 1 から N までの番号が振られており，
    出発地の駅は 1，目的地の駅は N と決まっている．
    路線図は2つの駅を結ぶ区間の列によって与えられる．
    区間はどちらの方向にも通行することができる．
    同じ駅同士を結ぶような区間は存在しないことと，
    ある駅の対を結ぶ区間はたかだか1つであることが保証されている．
  

  
Input

  

    入力は複数のデータセットからなる．
  

  

    それぞれのデータセットは次のような形式で与えられる．
  

  

    N M Z

    s1 d1

    s2 d2

    ...

    sM dM
  

  

    N は駅の総数，M は区間の総数であり，
    Z は切符に書かれたステップ数である．
    si と
    di (1 ≤ i ≤ M)
    は駅の番号を表す整数であり，
    それぞれ駅 si
    と駅 di
    の間に区間が存在することを表現している．
  

  

    N, M, Z
    は正の整数であり，次の条件を満たす：
    2 ≤ N ≤ 50,
    1 ≤ M ≤ 50,
    0 < Z < 231．
  

  

    最後のデータセットの後ろに， &ldquo;0 0 0&rdquo; と書かれた1行がある．
  

  

    データセットの数は30を越えない．
  

  
Output

  

    それぞれのデータセットに対し，
    チケットに書かれているステップ数ちょうどで
    目的地に到達できるならば &ldquo;yes&rdquo;，
    到達できないならば &ldquo;no&rdquo;
    のみを含む1行の文字列を出力せよ．
  

  
Sample Input

  

2 1 1
1 2
2 1 2
1 2
3 1 2
1 2
8 8 5778
1 2
2 3
2 4
3 5
5 6
6 7
7 8
4 8
8 8 5777
1 2
2 3
2 4
3 5
5 6
6 7
7 8
4 8
0 0 0

  
Output for the Sample Input

  

yes
no
no
yes
no



Sample input:
2 1 1
1 2
2 1 2
1 2
3 1 2
1 2
8 8 5778
1 2
2 3
2 4
3 5
5 6
6 7
7 8
4 8
8 8 5777
1 2
2 3
2 4
3 5
5 6
6 7
7 8
4 8
0 0 0


Sample output:
yes
no
no
yes
no

Submission status: Time Limit Exceeded

Solution code:
def dfs(s, t, z, links):
    stack = [(1, node, s) for node in links[s]]
    while stack:
        hop, node, ancestor = stack.pop()
        if hop > z:
            continue
        if node == t and hop == z:
            return True
        stack.extend((hop + 1, node2, node) for node2 in links[node] if node2 != ancestor)
    return False


while True:
    n, m, z = map(int, input().split())
    if not n:
        break
    links = [set() for _ in range(n)]
    for _ in range(m):
        s, d = map(int, input().split())
        links[s - 1].add(d - 1)
        links[d - 1].add(s - 1)
    print('yes' if dfs(0, n - 1, z, links) else 'no')

Submission status: Runtime Error

Solution code:
def main():
    while True:
        N, M, Z = map(int, raw_input().split())
        if N == 0:
            break
        L = []
        for _ in xrange(M):
            s, d = map(int, raw_input().split())
            L += [(s, d), (d, s)]
        L.sort()
        mat = Matrix(2*M, 2*M)
        for i, (pre, cur1) in enumerate(L):
            for j, (cur2, nex) in enumerate(L):
                if cur1 != cur2 or pre == nex:
                    continue
                mat[i][j] = 1
        init_mat = Matrix(2*M, 2*M)
        for i, (cur, nex) in enumerate(L):
            if cur != 1:
                continue
            for j in xrange(len(L)):
                init_mat[j][i] = 1
        fin_mat =  init_mat * mat ** (Z-1)
        for e, (cur, nex) in zip(fin_mat[0], L):
            if nex == N and e == 1:
                print "yes"
                break
        else:
            print "no"

class Matrix(list):
    def __init__(self, r, c, init=None):
        self.r, self.c = r, c
        list.__init__(self, [[0]*c for _ in xrange(r)])
        if init:
            for i, r in enumerate(init):
                for j, e in enumerate(r):
                    self[i][j] = e

    def __repr__(self):
        return "\n".join(map(str, self))

    def __mul__(self, mat):
        if self.r != mat.r or self.c != mat.c:
            raise Exception
        ret = Matrix(self.r, self.c)
        for i, r in enumerate(self):
            for j, c in enumerate(zip(*mat)):
                ret[i][j] = sum(e1 * e2 for e1, e2 in zip(r, c))
        return ret

    @classmethod
    def get_im(cls, n):
        ret = Matrix(n, n)
        for i in xrange(n):
            ret[i][i] += 1
        return ret

    def __pow__(self, n):
        if self.r != self.c:
            raise Exception
        ret = Matrix.get_im(self.r)
        x = Matrix(self.r, self.c, self)
        while n > 0:
            if (n & 1):
                ret = ret * x
            x = x * x
            n >>= 1
        return ret

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    while True:
        N, M, Z = map(int, raw_input().split())
        if N == 0:
            break
        L = []
        for _ in xrange(M):
            s, d = map(int, raw_input().split())
            L += [(s, d), (d, s)]
        L.sort()
        mat = Matrix(2*M, 2*M)
        for i, (pre, cur1) in enumerate(L):
            for j, (cur2, nex) in enumerate(L):
                if cur1 != cur2 or pre == nex:
                    continue
                mat[i][j] = 1
        init_mat = Matrix(2*M, 2*M)
        for i, (cur, nex) in enumerate(L):
            if cur != 1:
                continue
            for j in xrange(len(L)):
                init_mat[j][i] = 1
        fin_mat =  init_mat * mat ** (Z-1)
        for e, (cur, nex) in zip(fin_mat[0], L):
            if nex == N and e == 1:
                print "yes"
                break
        else:
            print "no"

class Matrix(list):
    def __init__(self, r, c, init=None):
        self.r, self.c = r, c
        list.__init__(self, [[0]*c for _ in xrange(r)])
        if init:
            for i, r in enumerate(init):
                for j, e in enumerate(r):
                    self[i][j] = e

    def __repr__(self):
        return "\n".join(map(str, self))

    def __mul__(self, mat):
        if self.r != mat.r or self.c != mat.c:
            raise Exception
        ret = Matrix(self.r, self.c)
        for i, r in enumerate(self):
            for j, c in enumerate(zip(*mat)):
                # ret[i][j] = sum(e1 * e2 for e1, e2 in zip(r, c))
                ret[i][j] = 1 if sum(e1 * e2 for e1, e2 in zip(r, c)) > 0 else 0
        return ret

    @classmethod
    def get_im(cls, n):
        ret = Matrix(n, n)
        for i in xrange(n):
            ret[i][i] += 1
        return ret

    def __pow__(self, n):
        if self.r != self.c:
            raise Exception
        ret = Matrix.get_im(self.r)
        x = Matrix(self.r, self.c, self)
        while n > 0:
            if (n & 1):
                ret = ret * x
            x = x * x
            n >>= 1
        return ret

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    while True:
        N, M, Z = map(int, raw_input().split())
        print N, M, Z
        if N == 0:
            break
        L = []
        for _ in xrange(M):
            s, d = map(int, raw_input().split())
            L += [(s, d), (d, s)]
        L.sort()
        mat = Matrix(2*M, 2*M)
        for i, (pre, cur1) in enumerate(L):
            for j, (cur2, nex) in enumerate(L):
                if cur1 != cur2 or pre == nex:
                    continue
                mat[i][j] = 1
        init_mat = Matrix(2*M, 2*M)
        for i, (cur, nex) in enumerate(L):
            if cur != 1:
                continue
            for j in xrange(len(L)):
                init_mat[j][i] = 1
        fin_mat =  init_mat * mat ** (Z-1)
        for e, (cur, nex) in zip(fin_mat[0], L):
            if nex == N and e == 1:
                print "yes"
                break
        else:
            print "no"

class Matrix(list):
    def __init__(self, r, c, init=None):
        self.r, self.c = r, c
        list.__init__(self, [[0]*c for _ in xrange(r)])
        if init:
            for i, r in enumerate(init):
                for j, e in enumerate(r):
                    self[i][j] = e

    def __repr__(self):
        return "\n".join(map(str, self))

    def __mul__(self, mat):
        if self.r != mat.r or self.c != mat.c:
            raise Exception
        ret = Matrix(self.r, self.c)
        for i, r in enumerate(self):
            for j, c in enumerate(zip(*mat)):
                # ret[i][j] = sum(e1 * e2 for e1, e2 in zip(r, c))
                ret[i][j] = 1 if any(e1 * e2 for e1, e2 in zip(r, c)) > 0 else 0
        return ret

    @classmethod
    def get_im(cls, n):
        ret = Matrix(n, n)
        for i in xrange(n):
            ret[i][i] += 1
        return ret

    def __pow__(self, n):
        if self.r != self.c:
            raise Exception
        ret = Matrix.get_im(self.r)
        x = Matrix(self.r, self.c, self)
        while n > 0:
            if (n & 1):
                ret = ret * x
            x = x * x
            n >>= 1
        return ret

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from itertools import izip as zip
def main():
    while True:
        N, M, Z = map(int, raw_input().split())
        if N == 0:
            break
        L = []
        for _ in xrange(M):
            s, d = map(int, raw_input().split())
            L += [(s, d), (d, s)]
        L.sort()
        mat = Matrix(2*M, 2*M)
        for i, (pre, cur1) in enumerate(L):
            for j, (cur2, nex) in enumerate(L):
                if cur1 != cur2 or pre == nex:
                    continue
                mat[i][j] = 1
        init_mat = Matrix(2*M, 2*M)
        for i, (cur, nex) in enumerate(L):
            if cur != 1:
                continue
            for j in xrange(len(L)):
                init_mat[j][i] = 1
        fin_mat =  init_mat * mat ** (Z-1)
        for e, (cur, nex) in zip(fin_mat[0], L):
            if nex == N and e == 1:
                print "yes"
                break
        else:
            print "no"

class Matrix(list):
    def __init__(self, r, c, init=None):
        self.r, self.c = r, c
        list.__init__(self, [[0]*c for _ in xrange(r)])
        if init:
            for i, r in enumerate(init):
                for j, e in enumerate(r):
                    self[i][j] = e

    def __repr__(self):
        return "\n".join(map(str, self))

    def __mul__(self, mat):
        if self.r != mat.r or self.c != mat.c:
            raise Exception
        ret = Matrix(self.r, self.c)
        for i, r in enumerate(self):
            for j, c in enumerate(zip(*mat)):
                # ret[i][j] = sum(e1 * e2 for e1, e2 in zip(r, c))
                ret[i][j] = any(e1 and e2 for e1, e2 in zip(r, c))
        return ret

    @classmethod
    def get_im(cls, n):
        ret = Matrix(n, n)
        for i in xrange(n):
            ret[i][i] += 1
        return ret

    def __pow__(self, n):
        import sys
        if self.r != self.c:
            raise Exception
        ret = Matrix.get_im(self.r)
        x = Matrix(self.r, self.c, self)
        while n > 0:
            #print n
            #sys.stdout.flush()
            if (n & 1):
                ret = ret * x
            x = x * x
            n >>= 1
        return ret

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from itertools import izip as zip
def main():
    while True:
        N, M, Z = map(int, raw_input().split())
        if N == 0:
            break
        L = []
        for _ in xrange(M):
            s, d = map(int, raw_input().split())
            L += [(s, d), (d, s)]
        #L.sort()
        mat = Matrix(2*M, 2*M)
        for i, (pre, cur1) in enumerate(L):
            for j, (cur2, nex) in enumerate(L):
                if cur1 != cur2 or pre == nex:
                    continue
                mat[i][j] = 1
        init_mat = Matrix(2*M, 2*M)
        for i, (cur, nex) in enumerate(L):
            if cur != 1:
                continue
            for j in xrange(len(L)):
                init_mat[j][i] = 1
        fin_mat =  init_mat * mat ** (Z-1)
        for e, (cur, nex) in zip(fin_mat[0], L):
            if nex == N and e == 1:
                print "yes"
                break
        else:
            print "no"

class Matrix(list):
    def __init__(self, r, c, init=None):
        self.r, self.c = r, c
        list.__init__(self, [[0]*c for _ in xrange(r)])
        if init:
            for i, r in enumerate(init):
                for j, e in enumerate(r):
                    self[i][j] = e

    def __repr__(self):
        return "\n".join(map(str, self))

    def __mul__(self, mat):
        #if self.r != mat.c or self.c != mat.r:
        #    raise Exception
        #ret = Matrix(self.r, self.c)
        #for i, r in enumerate(self):
            # for j, c in enumerate(zip(*mat)):
                # ret[i][j] = sum(e1 * e2 for e1, e2 in zip(r, c))
                # ret[i][j] = any(e1 * e2 for e1, e2 in zip(r, c))
        #return ret
        ret = ((any(e1 * e2 for e1, e2 in zip(r, c)) for c in zip(*mat)) for r in self)
        return Matrix(self.r, self.c, ret)

    @classmethod
    def get_im(cls, n):
        ret = Matrix(n, n)
        for i in xrange(n):
            ret[i][i] += 1
        return ret

    def __pow__(self, n):
        if self.r != self.c:
            raise Exception
        ret = Matrix.get_im(self.r)
        x = Matrix(self.r, self.c, self)
        while n > 0:
            if (n & 1):
                ret = ret * x
            x = x * x
            n >>= 1
        return ret

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from itertools import izip as zip
def main():
    while True:
        N, M, Z = map(int, raw_input().split())
        if N == 0:
            break
        L = []
        for _ in xrange(M):
            s, d = map(int, raw_input().split())
            L += [(s, d), (d, s)]
        #L.sort()
        mat = Matrix(2*M, 2*M)
        for i, (pre, cur1) in enumerate(L):
            for j, (cur2, nex) in enumerate(L):
                if cur1 != cur2 or pre == nex:
                    continue
                mat[i][j] = 1
        init_mat = Matrix(2*M, 2*M)
        for i, (cur, nex) in enumerate(L):
            if cur != 1:
                continue
            for j in xrange(len(L)):
                init_mat[j][i] = 1
        fin_mat =  init_mat * mat ** (Z-1)
        for e, (cur, nex) in zip(fin_mat[0], L):
            if nex == N and e == 1:
                print "yes"
                break
        else:
            print "no"

class Matrix(list):
    def __init__(self, r, c, init=None):
        self.r, self.c = r, c
        list.__init__(self, [[0]*c for _ in xrange(r)])
        if init:
            for i, r in enumerate(init):
                for j, e in enumerate(r):
                    self[i][j] = e

    def __repr__(self):
        return "\n".join(map(str, self))

    def __mul__(self, mat):
        #if self.r != mat.c or self.c != mat.r:
        #    raise Exception
        #ret = Matrix(self.r, self.c)
        #for i, r in enumerate(self):
        #    for j, c in enumerate(zip(*mat)):
        #        ret[i][j] = sum(e1 * e2 for e1, e2 in zip(r, c))
        #        ret[i][j] = any(e1 * e2 for e1, e2 in zip(r, c))
        #return ret
        ret = ((any(e1 and e2 for e1, e2 in zip(r, c)) for c in zip(*mat)) for r in self)
        return Matrix(self.r, self.c, ret)
    
    @classmethod
    def get_im(cls, n):
        ret = Matrix(n, n)
        for i in xrange(n):
            ret[i][i] += 1
        return ret

    def __pow__(self, n):
        if self.r != self.c:
            raise Exception
        ret = Matrix.get_im(self.r)
        x = Matrix(self.r, self.c, self)
        while n > 0:
            if (n & 1):
                ret = ret * x
            x = x * x
            n >>= 1
        return ret

if __name__ == "__main__":
    main()