为什么MLE
查看原帖
为什么MLE
669764
DragonForge楼主2025/1/26 17:57

为什么这段代码会 MLE

#include <bits/stdc++.h>

using namespace std;

const int MAXN=3010,KINF=1e9;

struct V{
	int h,d=-1;
	vector<pair<int,int>> e;
}v[MAXN];

int n,m,ans;

inline void B(){
	for(int i=1;i<=n&&!ans;i++){
		ans=1;
		for(int j=1;j<=n;j++){
			for(auto e: v[j].e){
				if(v[j].h>v[e.second].h+e.first){
					v[j].h=v[e.second].h+e.first;
					ans=0;
				}
			}
		}
	}
}

inline void D(int s){
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> h;
	for(int i=1;i<=n;i++){
		v[i].d=-1;
	}
	for(h.push({0,s});h.size();){
		auto p=h.top();
		h.pop();
		if(v[p.second].d=-1){
			v[p.second].d=p.first;
			for(auto e:v[p.second].e){
				h.push({v[e.second].h-v[p.second].h+e.first+p.first,e.second});
			}
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++){
		ans+=1LL*i*(v[i].d==-1?KINF:v[s].h-v[i].h+v[i].d);
	}
	cout<<ans<<'\n';
}

int main(void){
  //freopen(".in","r",stdin);
  //freopen(".out","w",stdout);
  cin.tie(0)->sync_with_stdio(false);
  cout.tie(0)->sync_with_stdio(false);
  cin>>n>>m;
  for(int i=1,x,y,z;i<=m;i++){
  	cin>>x>>y>>z;
  	v[x].e.emplace_back(z,y);
	}
	B();
	if(ans){
		for(int i=1;i<=n;i++){
			D(i);
		}
	}else{
		cout<<"-1";
	}
  return 0;
}

2025/1/26 17:57
加载中...