#includeiostream#includevector#includealgorithm#includecstringusing namespace std;const int INF=0x3f3f3f3f;int nesourcedestinationm;vectorpairintintgraph1005;int dp10051005;void dfsint uint cnt ifcnt

#include #include #include using namespace std; const int INF=0x3f3f3f3f; int n,e,source,destination,m; int graph[1005][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(int i=0;i<n;i++) { if(graph[u][i]!=INF) { dfs(i,cnt+1); dp[u][cnt]=min(dp[u][cnt],dp[i][cnt+1]+graph[u][i]); } } }

int main() { cin>>n>>e; memset(graph,INF,sizeof(graph)); for(int i=0; i<e; i++) { int u,v,w; cin>>u>>v>>w; graph[u][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; }