社区讨论
WA on #23求条 悬2关
P10166[DTCPC 2024] 环参与者 2已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @mkgfn643
- 此快照首次捕获于
- 2026/01/16 13:23 上个月
- 此快照最后确认于
- 2026/01/18 17:50 上个月
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+7;
int b[maxn],in[maxn],ans=1e16;
vector<int>a[maxn];
void dfs(int x,int sum){
for(auto i:a[x]){
ans=min(ans,sum+b[i]);
dfs(i,min(sum,b[i]));
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
a[u].push_back(v);
in[v]++;
}
for(int i=1;i<=n;i++){
if(!in[i]){
dfs(i,b[i]);
}
}
sort(b+1,b+n+1);
ans=min((b[1]+b[2])*2,ans);
cout<<ans;
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...