dij + 堆优化 90pts错误
查看原帖
dij + 堆优化 90pts错误
222578
jingkongwanglimiaoa楼主2020/11/21 13:55

rt,第七个点WA了,下载数据显示运行错误,可已经开了双倍空间啊

代码如下

# include <cstdio>
# include <cstring>
# include <queue>
using namespace std;
int n,p,lk[2510],hp = 0,u,v,ppp,dist[2510],s,t,vis[2510];
struct sth
{
	int pow,wei,power;
}e[15000];
struct node
{
	int user,dis;
	bool operator < (const node &x) const
	{
		return x.dis < dis;
	}
};
priority_queue <node> q;
void add(int xx,int yy,int pp)
{
	e[++hp] = {yy,lk[xx],pp};
	lk[xx] = hp;
}
void dij()
{
	while (!q.empty())
	{
		node sum = q.top();
		//printf("%d ",sum.user);
		q.pop();
		for (int i = lk[sum.user];i;i = e[i].wei)
		{
			
			if (dist[sum.user] + e[i].power < dist[e[i].pow]) 
			{
				dist[e[i].pow] = dist[sum.user] + e[i].power;
				if (!vis[e[i].pow])
				{
					vis[e[i].pow] = 1;
					q.push({e[i].pow,dist[e[i].pow]});			
				}
			}
		}

	}
}
int main()
{
	scanf("%d %d %d %d",&n,&p,&s,&t);
	memset(dist,0x3f,sizeof(dist));
	dist[s] = 0;vis[s] = 1;
	for (int i = 1;i <= p;i++)
	{
		scanf("%d %d %d",&u,&v,&ppp);
		add(u,v,ppp);add(v,u,ppp);
	}
//	printf("%d %d %d %d",n,p,s,t);
	q.push({s,0});
//	printf("%d",q.top().user);
	dij();
	printf("%d",dist[t]);
}
2020/11/21 13:55
加载中...