0pts 样例能过 求调
查看原帖
0pts 样例能过 求调
610349
tracy_yuxi楼主2024/10/24 21:18

思路就是先判断两条边的情况,再拓扑求

但不知道为啥一直过不了

#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;
}
2024/10/24 21:18
加载中...