求错
查看原帖
求错
1020370
ztt0430楼主2024/3/31 21:39

为什么过了标准版没过弱化版

using namespace std;
const int N=100004;
const int INF=INT_MAX-1;
struct node
{
	int to,val;
};
int n,m,s,dis[N],vis[N];
vector<node>edge[N];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > que;

void dij()
{
	que.push(make_pair(0,s));
	while(!que.empty())
	{
		int now=que.top().second;
		que.pop();
		if(vis[now]) 
		continue;
		vis[now]=1;
		for(int i=0;i<edge[now].size();i++)
		{
			int go=edge[now][i].to,v=edge[now][i].val;
			if(dis[now]+v<dis[go])
			{
				dis[go]=dis[now]+v;
				que.push(make_pair(dis[go],go));
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		edge[x].push_back({y,z});
	}
	for(int i=1;i<=n;i++)
	{
		if(i!=s)
		dis[i]=INF;
	}
	dij();
	for(int i=1;i<=n;i++)
	cout<<dis[i]<<" ";
	return 0;
}
2024/3/31 21:39
加载中...