求助大佬
查看原帖
求助大佬
1256176
CQnythy2012楼主2024/9/7 12:31

求大佬帮忙改正!,迪杰斯特拉90分,蒟蒻的我不知从何改起QAQ:

#include<bits/stdc++.h>
using namespace std;

const int inf=INT_MAX;
int n,m;
int path[3010],dist[3010];
bool fina[3010];
struct edge{
	int to,cost;
};
vector<edge> p[3010];
void dij(){
	for(int i=1;i<=n;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(fina[j]==false&&(t==-1||dist[j]<dist[t])){
				t=j;
			}
		}
		fina[t]=true;
		for(int j=0;j<p[t].size();j++){
			if(dist[p[t][j].to]>dist[t]+p[t][j].cost){
				path[p[t][j].to]=t;
				dist[p[t][j].to]=dist[t]+p[t][j].cost;
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		p[x].push_back((edge){y,1});
		p[y].push_back((edge){x,1});
	}
	for(int i=1;i<=n;i++){
		dist[i]=inf;
		path[i]=-1;
	}
	dist[1]=0;
	int s1,s2,t1,t2;
	cin>>s1>>t1>>s2>>t2;
	dij();
	if(dist[s1]>t1||dist[s2]>t2){
		cout<<"-1";
	}
	else{
		int ans=0;
		if(s1==s2){
			cout<<m-dist[s1];
		}
		else{
			int ans=0,i=s1;			
			while(i>1){
				int j=s2;
				while(j>1){
					if(i==j){
						ans++;
					}
					j=path[j];
				}
				i=path[i];
			}
			ans=m-dist[s1]-dist[s2]+ans;
			cout<<ans;
		}
	}
	return 0;
} 
2024/9/7 12:31
加载中...