Dij堆优化 样例能过 3MLE 3WA
查看原帖
Dij堆优化 样例能过 3MLE 3WA
1354472
a6b6c6d6楼主2025/1/16 14:39

为什么别人是TLE我是MLE???

https://www.luogu.com.cn/record/198505092

#include<bits/stdc++.h>
#define INF 0x7f
using namespace std;
vector<pair<int,int> >f[100001];
int dis[100001];
bool d[100001];
int n,m,s,a,b,c;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q; 
int main(){
	memset(dis,INF,sizeof(dis));
	memset(d,1,sizeof(d));
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		f[a].push_back(make_pair(b,c));
	}
	q.push(make_pair(s,0));
	dis[s]=0;
	while(!q.empty()){
		int x=q.top().first;
		q.pop();
		d[x]=0;
		for(int i=0;i<f[x].size();i++){
			dis[f[x][i].first]=min(dis[f[x][i].first],dis[x]+f[x][i].second);
			if(d[f[x][i].first]==1){
				q.push(make_pair(f[x][i].first,f[x][i].second));
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}
2025/1/16 14:39
加载中...