我这个代码是没问题的,但如果把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;
}