一个匪夷所思的问题
查看原帖
一个匪夷所思的问题
536337
eb0ycn楼主2023/11/10 21:20

我这个代码是没问题的,但如果把12行的 < 改成 > 就会TLE。这是什么鬼?

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
#define pii pair<int,int>
vector<pii>vec[N];

struct node
{
	int x,d;//位置 距离 
	bool operator< (const node& a) const
	{
		return a.d<d;//把距离小的定义为“大” 
	}
};

priority_queue<node>Q;//默认从大到小 
int n,m,s,x,y,dis[N],z;
void dij(int s)
{
	memset(dis,-1,sizeof(dis));
	dis[s]=0;
	Q.push({s,0});
	while(!Q.empty())
	{
		node u=Q.top();//u:当前点  
		Q.pop();
		if(u.d>dis[u.x])continue;
		for(pii ne:vec[u.x])
		{
			int np=ne.first;
			int nd=u.d+ne.second;
			if(dis[np]==-1||nd<dis[np])
			{
				dis[np]=nd;
				Q.push({np,nd});
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);//从x到y的边权是z 
		vec[x].push_back({y,z});
	}
	dij(s);
	for(int i=1;i<=n;++i)
	{
		printf("%d ",dis[i]);
	}
	return 0;
}
2023/11/10 21:20
加载中...