解題思路：比賽的是沒(méi)讀懂題意，這題求的是起點(diǎn)1到n路徑序列數(shù)，但是路徑序列上的相鄰兩個(gè)點(diǎn) i, i+1 之間應(yīng)該滿足 i、i+1 到終點(diǎn)的最短路low[i] > low[i+1]。
因此需要先以終點(diǎn)開(kāi)始，跑一遍dijkstra算法，考慮時(shí)間復(fù)雜度，使用鄰接表加優(yōu)先隊(duì)列優(yōu)化。計(jì)算得到最短路 low 數(shù)組，從起點(diǎn)dfs到終點(diǎn)的路徑數(shù)量，對(duì)于 i 節(jié)點(diǎn)，它到終點(diǎn)的路徑數(shù) dp[i] = sum(dp[ j ]) ( j 是滿足受限條件的下一個(gè)節(jié)點(diǎn) j，dp[j] 表示 j 到終點(diǎn)的路徑數(shù))；考慮到得數(shù)需要模1e7+7，因此可能會(huì)重復(fù)訪問(wèn)某個(gè)節(jié)點(diǎn)，因此用dp[i] 數(shù)組保存節(jié)點(diǎn) i 到終點(diǎn)的路徑數(shù)，減少重復(fù)的dfs次數(shù)。
（ps：用python寫(xiě)的代碼似乎有遞歸深度的限制，在一番折騰無(wú)解后，我用棧模擬了 dfs 過(guò)程。）
1 class Node(object):
2 def __init__(self,x,y):
3 self.id = x
4 self.dis = y
5
6 def __lt__(self, other): #定義了<，像C++的重載<運(yùn)算符
7 return self.dis<other.dis
8
9
10 import heapq
11 class PriorityQueue(object):
12 def __init__(self):
13 self._queue = []
14 self._index = 0
15 def push(self, item, priority):
16 # 傳入兩個(gè)參數(shù)，一個(gè)是存放元素的數(shù)組，另一個(gè)是要存儲(chǔ)的元素，這里是一個(gè)元組。
17 # 由于heap內(nèi)部默認(rèn)有小到大排，如果要從大到小排，就要對(duì)priority取負(fù)數(shù)
18 heapq.heappush(self._queue, (priority, self._index, item))
19 self._index += 1
20 def pop(self):
21 return heapq.heappop(self._queue)[-1]
22 def empty(self):
23 return not bool(len(self._queue))
24
25 class Solution(object):
26 def dij(self,n,vec):
27 inf = int(1e9)
28 used = [0]*n
29 low = [inf]*n
30 for i in range(n):
31 low[i] = inf
32 low[-1]=0
33 pq = PriorityQueue()
34 start = n-1
35 pq.push(start,low[n-1])
36 x= 0
37 while not pq.empty():
38 if x>=n:
39 break
40 now = pq.pop()
41 x+=1
42 #print(now.id)
43 for nxt in vec[now]:
44 if low[nxt.id] > low[now] + nxt.dis:
45 low[nxt.id] = low[now] + nxt.dis
46 pq.push(nxt.id,low[nxt.id])
47
48 return low
49
50 def countRestrictedPaths(self, n, edges):
51 sys.setrecursionlimit(100000)
52 inf = int(1e9)
53 vec = [[] for i in range(n)]
54 for edge in edges:
55 [s1,s2,w] = edge
56 n1,n2 = Node(s2-1,w),Node(s1-1,w)
57 vec[s1-1].append(n1)
58 vec[s2-1].append(n2)
59 #print(dis)
60 low = self.dij(n,vec)
61 #print('aaa')
62 dp = [0]*n
63 used = [0]*n
64 used[0] = 1
65 stack = [0]
66 while len(stack) >0:
67 top = stack.pop()
68 #print(stack)
69 stack.append(top)
70 if top == n-1: #終止條件
71 _ = stack.pop()
72 dp[top] = 1
73 used[top] = 0
74 continue
75 cnt = 0
76 flag = True
77 for nxt in vec[top]:
78 i = nxt.id
79 if low[top] > low[i] and used[i]==0:
80 if dp[i] == 0: #說(shuō)明沒(méi)有訪問(wèn)過(guò)，加入棧
81 #print('aaa',i)
82 used[i]=1
83 stack.append(i)
84 flag = False
85 break
86 else:
87 cnt= (cnt+dp[i])%(inf+7)
88 if not flag: #說(shuō)明要繼續(xù)搜索，當(dāng)前狀態(tài)不彈出
89 continue
90 dp[top] = cnt #記憶
91 _ = stack.pop()
92 used[top]=0
93 #print(self.dp)
94 #print(low)
95 return dp[0]
聯(lián)系客服
