为什么前两个测试点AC,后面就WA(下载数据在本地测试没问题)
查看原帖
为什么前两个测试点AC,后面就WA(下载数据在本地测试没问题)
631554
jefferw楼主2022/8/16 16:48

为什么前两个测试点AC,后面就WA(下载数据在本地测试没问题),代码:

#include <bits/stdc++.h>
#define MAX 100000
#define INF 4294967295//unsigned int最大能表示的数(2^32-1)
using namespace std;
struct edge
{
	int v;
	int w;
};
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
//表示是一对数,第一个是源点到任意点的距离距离,第二个是它相对应的点的编号
//greater:表示第一个数越小越优先
bool vis[MAX];
unsigned int dis[MAX],n,m,s;//dis:任意点到源点的距离距离
//存入pair的对象
vector<edge> e[MAX];//存储图的边
unsigned int ninf(unsigned int a,unsigned int b)//ninf:解决unsigned中inf加1等于0的问题
{
	if(a==INF||b==INF)return INF;
	else return a+b;
}
int dijk(int s)
{
	dis[s]=0;
	q.push(make_pair(0, s));//0:源点到任意点的距离距离  s:(源)点
	while(!q.empty())
	{
		int now=q.top().second;
		//现在的处理的点(找未加入集合s的dis中距离最小的点)
		q.pop();//删除堆顶的元素(pair对象)
		if(vis[now])continue;//如果vis[now]==1(加入了s),那么就退出这一次的循环
		vis[now]=1;
		
		//借东风
		for(auto& tmp : e[now])
		{
			
			if(dis[tmp.v]>ninf(dis[now],tmp.w))//ninf:解决unsigned中inf加1等于0的问题
			{
				dis[tmp.v]=ninf(dis[now],tmp.w);
				q.push(make_pair(dis[tmp.v],tmp.v));
			}
		}
	}
	return 0;
}
int main()
{
	memset(dis,255,sizeof(dis));
	memset(vis,0,sizeof(vis));
	scanf("%d%d%d",&n,&m,&s);
	for(int i=0;i<m;++i)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		edge tmp;
		tmp.v=v;
		tmp.w=w;
		e[u].push_back(tmp);
	}
	//计算结果
	dijk(s);
	//输出结果
	for(int i=1;i<=n;++i)
	{
		printf("%u ",dis[i]);
	}
}
2022/8/16 16:48
加载中...