C++ 最短路径算法实现 - 限制边数的路径查找

#include #include #include #include using namespace std;

const int INF=2147483647; int n,e,source,destination,m; vector<pair<int,int>>graph[1005]; int dp[1005][1005];

void dfs(int u,int cnt){ if(cnt>m)return; if(dp[u][cnt]!=INF)return; if(u==destination&&cnt==m){ dp[u][cnt]=0; return; } for(auto v:graph[u]){ dfs(v.first,cnt+1); dp[u][cnt]=min(dp[u][cnt],dp[v.first][cnt+1]+v.second); } }

int main(){ cin>>n>>e; for(int i=0;i<e;i++){ int u,v,w; cin>>u>>v>>w; graph[u].push_back({v,w}); } memset(dp,INF,sizeof(dp)); cin>>source>>destination>>m; dfs(source,0); if(dp[source][0]==INF)cout<<2147483647<<endl; else cout<<dp[source][0]<<endl; return 0; }