90pts求调
查看原帖
90pts求调
1354765
smzxyyc楼主2025/7/24 21:15
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,v[100005],sum,dp[100005]; 
vector<int>jy[200005];
queue<int>q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>a>>b;
    for(int i=0;i<n;i++){
        cin>>v[i];
	}
    for(int i=1;i<=m;i++){
    	int x,y;
    	cin>>x>>y;
        jy[x].push_back(y);
    }
    if(a==b){
    	cout<<0;
    	return 0;
	}
    memset(dp,0x3f,sizeof(dp));
	dp[a]=0;
	q.push(a);
    while(!q.empty()){
    	int u=q.front();
		q.pop();
    	for(int i=0;i<jy[u].size();i++){
    		if(dp[jy[u][i]]>dp[u]+1){
    			dp[jy[u][i]]=dp[u]+1;
    			q.push(jy[u][i]);
			}
		}
	}
    if(dp[b]==0x3f){
    	cout<<"No solution";
	}
	else{
		cout<<dp[b]+v[b]-v[a];
	}
    return 0;
}
2025/7/24 21:15
加载中...