紧急求助dijkstra优化版
  • 板块学术版
  • 楼主NASFsky
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/7/25 12:18
  • 上次更新2023/11/4 13:22:32
查看原帖
紧急求助dijkstra优化版
375403
NASFsky楼主2021/7/25 12:18

我的代码在测P4779时WA了,求大佬帮忙看一看我的代码,谢谢QAQ

#include <bits/stdc++.h>
#define inf 0x3f3f3f
#define N 100000+10
using namespace std;
struct node{int to,dis;};
bool vis[N];
int dis[N];
int s,n,m;
vector<node>g[2*N];
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
	cin>>n>>m>>s; 
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		g[u].push_back((node){v,w});
	}
	memset(dis,inf,sizeof(dis));
	dis[s]=0;q.push(s);
	while(!q.empty())
	{
		int u=q.top();q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].to;
			if(dis[v]>dis[u]+g[u][i].dis)
			{
				dis[v]=dis[u]+g[u][i].dis;
				q.push(v);
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}
2021/7/25 12:18
加载中...