お世話になっております。
AOJ 1058 Winter Bells
こちらの問題についてpython3で実装を行ったのですが、何度やってもTLEになってしまいます。
基本的な解法はあってるとは思うのですが、最適な解き方とは自分でも思えず、色んな部分にボトルネックがありそうです。
ただ、どうしても自分ではどこをどう直せば改善するかわからないので、ご教授願えないでしょうか。
よろしくお願い致します。
下記にコードを記述します。
日本語コメントを記載していますが、削除しないとAOJ上ではランタイムエラーになります。
python
1vertex,edge,children = (int(n) for n in input().split(' ')) 2while True: 3 if children == 0: 4 print(0) 5 vertex,edge,children = (int(n) for n in input().split(' ')) 6 if vertex == 0 and edge == 0 and children == 0: 7 break 8 else: 9 continue 10 graph = [] 11 child = [] 12 for e in range(edge): 13 graph.append([int(n) for n in input().split(' ')]) 14 for c in range(children): 15 child.append(int(input())) 16 stack = [[0,0,[]]] 17 root = [] 18 destination = [] 19 mindist = {} 20 destnum = 0 21 childnum = {} 22 while len(stack) > 0: 23 stack = sorted(stack,key = lambda x:x[1]) 24 start,weight,dream = stack[0][0],stack[0][1],stack[0][2] 25#最短経路より重みが大きい物は枝刈り 26 if stack[0][0] in root and weight > mindist[stack[0][0]]: 27 stack.pop(0) 28 continue 29#最終地点の最短経路の重みより大きいスタックになった時点で終了 30 elif mindist.get(vertex-1) != None and stack[0][1] > mindist[vertex - 1]: 31 break 32 33 for gr in graph: 34#現在地点の頂点と辺の始点が一致していて最短経路が判明していないもの 35 if gr[0] == start and gr[0] not in root: 36#経路上で子供が見ているかどうかの計算 37 if gr[1] not in child: 38 stack.append([gr[1],weight + gr[2],dream]) 39 elif gr[1] in child and gr[1] not in dream: 40 disp = dream.copy() 41 disp.append(gr[1]) 42 stack.append([gr[1],weight + gr[2],disp]) 43#現在地点の頂点と辺の始点が一致する且つ最短経路が判明していてその最短経路 44#の重みと等しい物 45 elif gr[0] == start and mindist.get(gr[0]) != None and weight == mindist[gr[0]]: 46 47#経路上で子供が見ているかどうかの計算 48 49 if gr[1] in child: 50 disp = dream.copy() 51 disp.append(gr[1]) 52 stack.append([gr[1],weight + gr[2],disp]) 53 else: 54 stack.append([gr[1],weight + gr[2],dream]) 55#最短経路が判明したものの追加 56 if stack[0][0] not in root: 57 root.append(stack[0][0]) 58 mindist[stack[0][0]] = stack[0][1] 59#最終地点に到着したスタックについての計算 60 if stack[0][0] == vertex - 1 : 61 destination.append(stack[0]) 62 destnum += 1 63 for c in range(len(stack[0][2])): 64 if childnum.get(stack[0][2][c]) == None: 65 childnum[stack[0][2][c]] = 1 66 else: 67 childnum[stack[0][2][c]] += 1 68 stack.pop(0) 69 for c in child: 70 if c == 0: 71 print(1) 72 else: 73 if childnum.get(c) == None: 74 print(0) 75 else: 76 print(childnum[c] / destnum) 77 print("") 78 vertex,edge,children = (int(n) for n in input().split(' ')) 79 if vertex == 0 and edge == 0 and children == 0: 80 break
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。