Record Link

rt，用的Dijkstra算法

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10;
int n,m;
int g[N][N];
int s[N];
bool vis[N];
int ans[N];
//创建了一个小根堆
struct Node
{
	int to; //终点
	int w; //边权
};
template<class T>
class cmp
{
	public:bool operator()(T A,T B){return A.w>B.w;}
};
priority_queue<Node,vector<Node>,cmp<Node>> q;
//朴素版dijkstra 时间复杂度 O(n^2)
void dijkstra(int k)
{
	//q堆初始化：起点与其他结点的距离计算出来放进s集合
	for(int i=2;i<=n;i++)
	{
		if(g[k][i]==0) g[k][i]=INT_MAX;
		q.push(Node{i,g[k][i]});
	}
	//每次循环处理掉一个点（起点除外）
	for(int i=1;i<n;i++)
	{
		//在堆里面找最小值
		Node p=q.top(); q.pop();
		//以当前点作为中转点更新其他点到起点的距离
		for(int j=1;j<=n;j++)
		{
			int dis=(g[p.to][j]==INT_MAX)?(INT_MAX):(p.w+g[p.to][j]);
			if(dis!=INT_MAX) q.push({j,dis});
		}
	}
	vis[k]=1;
	while(!q.empty())
	{
		Node p=q.top();q.pop();
		if(!vis[p.to])
		{
			ans[p.to]=p.w;
			vis[p.to]=1;
		}
	}
}
signed main()
{
	int start;
	cin>>n>>m>>start;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u][v]=g[v][u]=w;
	}
	dijkstra(start);
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}

不加堆优化的：

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10;
int n,m;
int g[N][N];
int s[N];
bool vis[N];
//朴素版dijkstra 时间复杂度 O(n^2)
void dijksrta(int k)
{
	//s集初始化：起点与其他结点的距离计算出来放进s集合
	for(int i=1;i<=n;i++) s[i]=g[k][i];
	s[k]=0,vis[k]=1;
	int cur=k;
	//每次循环处理掉一个点（起点除外）
	for(int i=1;i<n;i++)
	{
		int minn=INT_MAX;
		//在s集里面找最小值
		for(int j=1;j<=n;j++)
		{
			if(!vis[j]&&s[j]<minn)
			{
				minn=s[j],cur=j;
			}
		}
		vis[cur]=1;
		s[cur]=minn;  //以当前点作为中转点更新其他点到起点的距离
		for(int j=1;j<=n;j++)
		{
			int dis=(g[cur][j]==INT_MAX)?(INT_MAX):(minn+g[cur][j]);
			if(!vis[j]&&dis<s[j]) s[j]=dis;
		}
	}
}
signed main()
{
	int start;
	cin>>n>>m>>start;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u][v]=g[v][u]=w;
	}
	dijksrta(start);
	for(int i=1;i<=n;i++) cout<<s[i]<<" ";
	return 0;
}