单元最短路(dijkstra)模板

#include<bits/stdc++.h>
using namespace std;
int n,m,a[505][505],dis[505],k;
void dijkstra(int x)
{
	int f[505];
	memset(dis,0x3f,sizeof(dis));
	memset(f,0,sizeof(f));
	dis[x]=0;
	for(int i=1;i<=n;i++)
	{
		int t=0;
		for(int j=1;j<=n;j++)
		{
			if(f[j]==0&&dis[j]<dis[t])
			{
				t=j;
			}
		}
		if(t==0)
		{
			return ;
		}
		f[t]=1;
		for(int j=1;j<=n;j++)
		{
			if(dis[j]>dis[t]+a[t][j])
			{
				dis[j]=dis[t]+a[t][j];
			}
		}
	}
	return ;
}
int main()
{
	cin>>n>>m>>k;
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=min(a[x][y],z);
	}
	dijkstra(1);
	if(dis[k]==0x3f3f3f3f)
	{
		cout<<-1;
	}
	else
	{
		cout<<dis[k];
	}
	return 0;
} 

#include<bits/stdc++.h>
using namespace std;
int n,m,k,head[100005],cnt,dis[100005];
struct abc
{
	int to,size,next;
}a[100005];
void add(int x,int y,int z)
{
	cnt++;
	a[cnt].to=y;
	a[cnt].next=head[x];
	a[cnt].size=z;
	head[x]=cnt;
	return ;
}
void dijkstra(int x)
{
	int f[100005];
	memset(dis,0x3f,sizeof(dis));
	memset(f,0,sizeof(f));
	dis[x]=0;
	for(int i=1;i<=n;i++)
	{
		int t=0;
		for(int j=1;j<=n;j++)
		{
			if(f[j]==0&&dis[j]<dis[t])
			{
				t=j;
			}
		}
		if(t==0)
		{
			return ;
		}
		f[t]=1;
		for(int j=head[t];;j=a[j].next)
		{
			if(j==0)
			{
				break;
			}
			if(dis[a[j].to]>dis[t]+a[j].size)
			{
				dis[a[j].to]=dis[t]+a[j].size;
			}
		}
	}
	return ;
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dijkstra(1);
	if(dis[k]==0x3f3f3f3f)
	{
		cout<<-1;
	}
	else
	{
		cout<<dis[k];
	}
	return 0;
} 

#include<bits/stdc++.h>
using namespace std;
int n,m,k,head[100005],cnt,dis[100005];
priority_queue< pair<int,int> ,vector< pair<int,int> >,greater< pair<int,int> > > q;
struct abc
{
	int to,size,next;
}a[100005];
void add(int x,int y,int z)
{
	cnt++;
	a[cnt].to=y;
	a[cnt].next=head[x];
	a[cnt].size=z;
	head[x]=cnt;
	return ;
}
void dijkstra(int x)
{
	int f[100005];
	memset(dis,0x3f,sizeof(dis));
	memset(f,0,sizeof(f));
	dis[x]=0;
	q.push({0,x});
	while(!q.empty())
	{
		pair<int,int> t=q.top();
		q.pop();
		if(f[t.second]==1)
		{
			continue;
		}
		f[t.second]=1;
		for(int i=head[t.second];;i=a[i].next)
		{
			if(i==0)
			{
				break;
			}
			if(dis[a[i].to]>t.first+a[i].size)
			{
				dis[a[i].to]=t.first+a[i].size;
				q.push({dis[a[i].to],a[i].to});
			}
		}
	}
	return ;
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dijkstra(1);
	if(dis[k]==0x3f3f3f3f)
	{
		cout<<-1;
	}
	else
	{
		cout<<dis[k];
	}
	return 0;
}