dijkstra模板

dijkstra最短路

priority_queue<pii,vector<pii>,greater<pii> >q;
for(int i=0;i<2*N+10;i++)dis[i]=inf;
dis[st]=0;
q.push(pii(0,st));//first-路程 second-序号
while(!q.empty()){
	pii u=q.top();
	q.pop();
	int x=u.se,sum=u.fi;
	if(sum>dis[x])continue;
	for(auto v:t[x]){
		int y=v.fi,z=v.se;//v.fi-nxt点 v.se-w边权
		if(dis[y]>sum+z){
			dis[y]=sum+z;
			q.push(pii(dis[y],y));
		}
	}
}