文章目錄
1. 題目
現有一個加權無向連通圖。
給你一個正整數 n ，表示圖中有 n 個節點，并按從 1 到 n 給節點編號；另給你一個數組 edges ，其中每個 edges[i] = [ui, vi, weighti] 表示存在一條位于節點 ui 和 vi 之間的邊，這條邊的權重為 weighti 。
從節點 start 出發到節點 end 的路徑是一個形如 [z0, z1, z2, ..., zk] 的節點序列，滿足 z0 = start 、zk = end 且在所有符合 0 <= i <= k-1 的節點 zi 和 zi+1 之間存在一條邊。
路徑的距離定義為這條路徑上所有邊的權重總和。
用 distanceToLastNode(x) 表示節點 n 和 x 之間路徑的最短距離。
受限路徑 為滿足 distanceToLastNode(zi) > distanceToLastNode(zi+1) 的一條路徑，其中 0 <= i <= k-1 。
返回從節點 1 出發到節點 n 的 受限路徑數 。
由于數字可能很大，請返回對 10^9 + 7 取余 的結果。
示例 1：
輸入：n
= 5,
edges
= [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
輸出：
3
解釋：每個圓包含黑色的節點編號和藍色的 distanceToLastNode 值。
三條受限路徑分別是：
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5
示例 2：
輸入：n
= 7,
edges
= [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
輸出：
1
解釋：每個圓包含黑色的節點編號和藍色的 distanceToLastNode 值。
唯一一條受限路徑是：
1 --> 3 --> 7 。提示：
1 <= n
<= 2 * 10^4
n
- 1 <= edges
.length
<= 4 * 10^4
edges
[i
].length
== 3
1 <= ui
, vi
<= n
ui
!= vi
1 <= weighti
<= 10^5
任意兩個節點之間至多存在一條邊
任意兩個節點之間至少存在一條路徑
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-restricted-paths-from-first-to-last-node
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
- 先預處理出每個點 到 n 點 的最短路徑，參考迪杰斯特拉算法
- 再建立 1 開始的最短路徑是遞減的 新圖，同時記錄節點的入度
- 采用 拓撲排序，累積前一個節點轉移過來的方案數
typedef pair
<int, int> pii
;
struct cmp
{bool operator()(pii
& a
, pii
& b
) const{return a
.first
> b
.first
;}
};
class Solution {
public:int countRestrictedPaths(int n
, vector
<vector
<int>>& edges
) {vector
<unordered_map
<int,int>> g(n
);for(auto & e
: edges
){g
[e
[0]-1][e
[1]-1] = e
[2];g
[e
[1]-1][e
[0]-1] = e
[2];}vector
<int> dis(n
, INT_MAX
);priority_queue
<pii
, vector
<pii
>, cmp
> q
;dis
[n
-1] = 0;q
.push({0, n
-1});while(!q
.empty()){pii tp
= q
.top();int d
= tp
.first
;int id
= tp
.second
;q
.pop();for(auto it
= g
[id
].begin(); it
!= g
[id
].end(); ++it
){int nid
= it
->first
;int nd
= it
->second
;if(d
+ nd
< dis
[nid
]){dis
[nid
] = d
+ nd
;q
.push({dis
[nid
], nid
});}}}vector
<int> indegree(n
, 0);unordered_map
<int,unordered_set
<int>> g2
;queue
<int> q1
;q1
.push(0);unordered_set
<int> vis
;vis
.insert(0);while(!q1
.empty()){int id
= q1
.front();q1
.pop();for(auto it
= g
[id
].begin(); it
!= g
[id
].end(); ++it
){int nid
= it
->first
;if(dis
[id
] > dis
[nid
]){g2
[id
].insert(nid
);indegree
[nid
]++;if(!vis
.count(nid
)){vis
.insert(nid
);q1
.push(nid
);}}}}long long mod
= 1e9+7;vector
<long long> ans(n
, 0);ans
[0] = 1;queue
<int> q2
;q2
.push(0);while(!q2
.empty()){int id
= q2
.front();q2
.pop();for(auto it
= g2
[id
].begin(); it
!= g2
[id
].end(); ++it
){int nid
= *it
;ans
[nid
] = (ans
[nid
] + ans
[id
])%mod
;if(--indegree
[nid
] == 0)q2
.push(nid
);}}return ans
[n
-1]%mod
;}
};
676 ms 174 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 1786. 从第一个节点出发到最后一个节点的受限路径数（迪杰斯特拉 + 拓扑排序）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
