1 条题解
-
0
按逆拓扑顺序求最优后继,地雷数为零时也走到无后继的地窖;使用 long long 累加。
#include <bits/stdc++.h> using namespace std; int main(){int n;cin>>n;vector<long long>a(n),d(n);vector<vector<int>>edge(n);vector<int>next(n,-1);for(auto&x:a)cin>>x;int u,v;while(cin>>u>>v&&(u||v))edge[u-1].push_back(v-1);for(int i=n-1;i>=0;i--){d[i]=a[i];sort(edge[i].begin(),edge[i].end());if(!edge[i].empty()){int best=edge[i][0];for(int j:edge[i])if(d[j]>d[best])best=j;d[i]+=d[best];next[i]=best;}}int s=max_element(d.begin(),d.end())-d.begin();cout<<s+1;for(int u=next[s];u>=0;u=next[u])cout<<'-'<<u+1;cout<<"\n"<<d[s]<<"\n";}
- 1
信息
- ID
- 3937
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 4
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者