3个点wa萌新求助
查看原帖
3个点wa萌新求助
218223
chenxsir楼主2020/6/9 13:47

真的不知道怎么改了

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=100100,INF=0x3f3f3f3f;
int n,m,s;
int dis[maxn],book[maxn];
struct pp
{
	int d,u;
	bool operator < (const pp& lss) const
	{
		return d>lss.d;
	}
};
vector<pp> g[maxn];
void dijkstra(int s);
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		pp a,b;
		cin>>a.u>>b.u>>a.d;
		b.d=a.d;
		g[a.u].push_back(b);
		g[b.u].push_back(a);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
	return 0;
}
void dijkstra(int s)
{
	priority_queue<pp> duil;
	memset(dis,0x3f,sizeof dis);
	pp lsa; lsa.u=s; lsa.d=0;
	duil.push(lsa);
	dis[s]=0;
	while(!duil.empty())
	{
		pp lsx=duil.top(); duil.pop();
		int lu=lsx.u; //cout<<"ds"<<endl;
		if(book[lu]) continue;
		book[lu]=1;
		for(int i=0;i<g[lu].size();i++)
		{
			int le=g[lu][i].u;
			int ld=g[lu][i].d; //cout<<le<<endl;
			if(dis[le]>dis[lu]+ld)
			{
				dis[le]=dis[lu]+ld;
				pp lsg; lsg.u=le; lsg.d=dis[le];
				duil.push(lsg);
			}
		}
	}
}
2020/6/9 13:47
加载中...