a259 - 10917 - A Walk Through the Forest
題目描述
題目描述了在一個森林中尋找從起點（辦公室）到終點（家）的多種路徑，要求路徑必須“前進”，即選擇的下一個點到家的距離必須比當前點到家的距離更短。目標是計算有多少種不同的路徑可以從起點走到終點。
解題思路
本題的核心思想是利用 Dijkstra 演算法計算每個節點到終點（編號為 2）的最短距離，然後使用深度優先搜尋 (DFS) 統計從起點（編號為 1）到終點的有效路徑數量。
- Dijkstra 演算法: 使用優先佇列 (priority queue) 實現 Dijkstra 演算法，計算每個節點到終點的最短距離。
dp[i]儲存節點i到終點的最短距離。 - DFS 搜尋: 從起點開始，使用 DFS 搜尋所有可能的路徑。在 DFS 的過程中，只考慮那些到終點距離比當前節點更短的鄰居節點。
dp2[x]儲存從節點x出發到終點的不同路徑數量。 - 路徑計數: 在 DFS 的過程中，遞迴地計算路徑數量。如果一個節點
x的dp[x]大於當前節點y的dp[y]，則表示從x出發的路徑是“前進”的，可以遞迴地計算從x出發的路徑數量，並將其加到dp2[y]中。
複雜度分析
- 時間複雜度: O(M log N + N * E)，其中 N 是節點數量，M 是邊的數量，E 是鄰居節點的數量。Dijkstra 演算法的時間複雜度為 O(M log N)，DFS 搜尋的時間複雜度為 O(N * E)。
- 空間複雜度: O(N)，主要用於儲存
dp、dp2陣列和鄰接表。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n,m,dp[1001],ans,dp2[1001];
vector <pair <int,int>> e[1001];
int dfs(int x){
if(dp2[x]!=-1)return dp2[x];
dp2[x]=0;
for(int i=0;i<e[x].size();++i)
if(dp[e[x][i].first]>dp[x])
dp2[x]+=dfs(e[x][i].first);
return dp2[x];
}
int main(){
while(scanf("%d", &n) == 1 && n){
scanf("%d",&m);
ans=0;
for(int i=1;i<=n;++i){
dp[i]=dp2[i]=-1;
e[i].clear();
}
for(int i=0,x,y,z;i<m;++i){
scanf("%d %d %d,",&x,&y,&z);
e[x].push_back({y,z});
e[y].push_back({x,z});
}
priority_queue <pair <int,int>,vector <pair <int,int>>,greater <pair <int,int>>> pq;
pq.push({0,2});
while(!pq.empty()){
int v=pq.top().first,it=pq.top().second;
pq.pop();
if(dp[it]!=-1)continue;
dp[it]=v;
for(int i=0;i<e[it].size();++i){
if(dp[e[it][i].first]!=-1)continue;
pq.push({v+e[it][i].second,e[it][i].first});
}
}
dp2[1]=1;
printf("%d\n",dfs(2));
}
}