dijkstra板子

优先队列优化 时间复杂度O(mlogn)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct node{
   
	int a,b;
	node(int _a,int _b):a(_a),b(_b){
   
	}
	node(){
   
	}
	friend bool operator < (node a,node b){
   
		return a.b>b.b;
	}
};
vector<node> v[2500];
int d[2500];
bool vis[2500];
int tot;
void di(){
   
	priority_queue<node> q;
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[1]=0;
	q.push(node(1,0));
	while(!q.empty()){
   
		int x=q.top().a;
		q.pop();
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=0;i<v[x].size();i++){
   
			int y=v[x][i].a,z=v[x][i].b;
			if(d[y]>d[x]+z){
   
				d[y]=d[x]+z;
				q.push(node(y,d[y]));
			}
		}
	}
}
int main(){
   
	int n,m;	// n是边的个数，m是终点
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
   
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		v[a].push_back((node(b,c)));
		v[b].push_back((node(a,c)));
	}
	di();
	printf("%d\n",d[m]); 
	return 0;
}