思路就是先判断两条边的情况,再拓扑求
但不知道为啥一直过不了
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
int n,m;
vector<int>g[N];
int in[N];
int dp[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i],dp[i]=a[i];
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
g[u].push_back(v);in[v]++;
}
int ans=0;
int min1=0x3f3f3f3f,min2=0x3f3f3f3f;
for(int i=1;i<=n;i++){
if(a[i]<=min1)min2=min1,min1=a[i];
else if(a[i]<min2)min2=a[i];
}
ans=min1+min2<<1;
queue<int>q;
for(int i=1;i<=n;i++)
if(!in[i])q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
for(int u:g[x]){
ans=min(ans,a[u]+dp[x]),dp[u]=min(dp[x],dp[u]);
in[u]--;if(!in[u])q.push(u);
}
}
for(int i=1;i<=n;i++)if(in[i])ans=0;
cout<<ans;
return 0;
}