dijkstra算法-526互联

【USACO】热浪

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int u,dist;
	node(int _u,int _dist)
	{
		u=_u;
		dist=_dist;
	}
};
struct node2
{
	int v,w;
	node2(int _v,int _w)
	{
		v=_v;
		w=_w;
	}
};
struct cmp
{
	bool operator()(node a,node b)
	{
		return a.dist>b.dist;
	}
};
priority_queue<node,vector<node>,cmp> q;
vector<node2> g[6201];
int c,t,ts,te,d[2501];
bool vis[2501];
void dijkstra(int o)
{
	memset(d,88,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[o]=0;
	q.push(node(o,0));
	while(q.size())
	{
		int x=q.top().u;
		q.pop();
		vis[x]=true;
		for(int i=0;i<g[x].size();i++){
			int y=g[x][i].v;
			int z=g[x][i].w;
			if(!vis[y]&&d[x]+z<d[y]){
				d[y]=d[x]+z;
				q.push(node(y,d[y]));
			}
		}
	}
}
int main()
{
	cin>>t>>c>>ts>>te;
	for(int i=1;i<=c;i++){
		int rs,re,ci;
		cin>>rs>>re>>ci;
		g[rs].push_back({re,ci});
		g[re].push_back({rs,ci});
	}
	dijkstra(ts);
	cout<<d[te];
	return 0;
}

算法

dijkstra