2503:Project Management
DAGが与えられるので、最長経路を求める問題。
ただしノードPで作業を開始するためには
Pまでの最長日数が経っている必要がある。
トポロジカルソートしてからDPした。
dp[i]:=結合点iまでの最長日数
#include<iostream> #include<algorithm> #include<vector> #define INF 100000000 using namespace std; int graph[400][400],n,dp[400]; bool visit[400]; vector<int>L; void Tsort(int v){ visit[v]=true; for(int i=0;i<n;i++) if(graph[v][i]>0 && !visit[i])Tsort(i); L.push_back(v); } int main(void){ int m,a,b,c; cin >> n >> m; for(int i=0;i<m;i++){ cin >> a >> b >> c; graph[a][b]=c; } Tsort(0); reverse(L.begin(),L.end()); for(int i=1;i<L.size();i++) for(int j=0;j<L.size();j++) if(graph[L[j]][L[i]]>0) dp[L[i]]=max(dp[L[i]],dp[L[j]]+graph[L[j]][L[i]]); cout << dp[n-1] << endl; return 0; }