68分求助(赏关)
查看原帖
68分求助(赏关)
380406
allqpsi楼主2023/11/14 12:27

PLZ help me

#include<bits/stdc++.h>
using namespace std;
struct node{
	int x,y;
	bool operator<(node l)const{
		return y>l.y;
	}
};
int n,m,x1,yx,x2,ans=-99999999,yy,a,b,c,linx[300005],liny[300005],linw[300005],in[1505],di[1505][1505];
vector<node>vi[1505];
bool vis[1505];
priority_queue<node>qi;
queue<int>qi2;
void dij(int st){
	for(int i=1;i<=n;i++){
		di[st][i]=999999999;
	}
	memset(vis,false,sizeof(vis));
	di[st][st]=0;
	qi.push(node{st,0});
	while(!qi.empty()){
		int x=qi.top().x,y=qi.top().y;
		qi.pop();
		if(vis[x]){
			continue;
		}
		vis[x]=true;
		for(int i=0;i<vi[x].size();i++){
			int nx=vi[x][i].x,ny=vi[x][i].y;
			if(y+ny<di[st][nx]){
				di[st][nx]=y+ny;
				qi.push(node{nx,di[st][nx]});
			}
		}
	}
}
void topo(){
	di[0][0]=-99999999;
	for(int i=1;i<=n;i++){
		di[0][n]=-99999999;
		if(in[i]==0){
			qi2.push(i);
			di[0][i]=0;
		}
	}
	while(!qi2.empty()){
		int x=qi2.front();
		qi2.pop();
		for(int i=0;i<vi[x].size();i++){
			int y=vi[x][i].x,w=vi[x][i].y;
			in[y]--;
			if(in[y]==0){
				qi2.push(y);
			}
			if(di[0][x]!=di[0][0]){
				if(di[0][y]<di[0][x]+w){
					di[0][y]=di[0][x]+w;
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>x1>>yx>>x2>>yy;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		linx[i]=a;
		liny[i]=b;
		linw[i]=c;
		linx[i+m]=b;
		liny[i+m]=a;
		linw[i+m]=c;
		vi[a].push_back(node{b,c});
		vi[b].push_back(node{a,c});
	}
	dij(x1);
	dij(yx);
	dij(x2);
	dij(yy);
	for(int i=1;i<=n;i++){
		while(!vi[i].empty()){
			vi[i].pop_back();
		}
	}
	for(int i=1;i<=2*m;i++){
		if(di[x1][linx[i]]+linw[i]+di[yx][liny[i]]==di[x1][yx]&&di[x2][linx[i]]+linw[i]+di[yy][liny[i]]==di[x2][yy]){
			vi[linx[i]].push_back(node{liny[i],linw[i]});
			in[liny[i]]++;
		}
	}
	topo();
	for(int i=1;i<=n;i++){
		ans=max(ans,di[0][i]);
		while(!vi[i].empty()){
			vi[i].pop_back();
		}
	}
	memset(in,0,sizeof(in));
	for(int i=1;i<=2*m;i++){
		if(di[x1][linx[i]]+linw[i]+di[yx][liny[i]]==di[x1][yx]&&di[yy][linx[i]]+linw[i]+di[x2][liny[i]]==di[x2][yy]){
			vi[linx[i]].push_back(node{liny[i],linw[i]});
			in[liny[i]]++;
		}
	}
	topo();
	for(int i=1;i<=n;i++){
		ans=max(ans,di[0][i]);
	}
	cout<<ans;
}
2023/11/14 12:27
加载中...