P1339

迪杰斯特拉堆优化

#include<bits/stdc++.h>
using namespace std;
int head[1000004],tot,dis[1000004],v[100004];
int n,m,s,t;
priority_queue<pair<int,int> >q;
struct hh{
	int next,to,w;
}edge[10000005];
void add(int a,int b,int c){
	edge[++tot].to=b;
	edge[tot].next=head[a];
	edge[tot].w=c;
	head[a]=tot;
}
void Dijkstra(){
	dis[s]=0;
	q.push(make_pair(0,s));
	while(q.size()>0){
		int x=q.top().second;
		q.pop();
		if(v[x])continue;
		v[x]=1;
		for(int i=head[x];i;i=edge[i].next){
			int y=edge[i].to;
			if(!v[i]&&dis[y]>dis[x]+edge[i].w){
				dis[y]=dis[x]+edge[i].w;
				q.push(make_pair(-dis[y],y));
			}
		}
	}
}
int main(){
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	memset(dis,1e9,sizeof dis);
	memset(v,0,sizeof v);
	Dijkstra();
	cout<<dis[t];
	return 0;
}

中的

q.push(make_pair(-dis[y],y));

为啥是

-d[y]

呀

帮帮我