求邻接表存图题解
查看原帖
求邻接表存图题解
1053122
shy_lihui楼主2024/11/6 23:46

rt,或能不能帮帮我优化一下代码

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int x;
	int w;
};
int n,m,s;
vector<node> e[100005];
int a[100005];
priority_queue<int,vector<int>,greater<int>> q;
//priority_queue<int> q;
void dijkstra(int s)
{
	q.push(s);
	a[s]=0;
	while(!q.empty())
	{
		int u=q.top();
		q.pop();
		for(int i=0;i<e[u].size();i++)
		{
			node v=e[u][i];
			if(a[v.x]>a[u]+v.w)
			{
				a[v.x]=a[u]+v.w;
				q.push(v.x);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(a,0x3f3f3f3f3f3f,sizeof(a));
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0x3f3f3f3f)
		{
			cout<<(1<<31)-1<<' ';
		}
		else
		{
			cout<<a[i]<<' ';
		}
	}
	return 0;
}
2024/11/6 23:46
加载中...