求助!为什么代码有三个点RE了呀?
查看原帖
求助!为什么代码有三个点RE了呀?
74430
yuzh0816楼主2024/10/14 19:29

代码见下,求大佬帮忙解决下,谢谢!

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x7f7f7f7f

int n,m,k,s,t;

struct node
{
	int id;
	int dis;
	bool operator< (const node& x) const {
		return x.dis < dis;
	}
};

struct Edge{
	int from, to, weight, next;
}edge[1000010];
int head[1000010], cnt=0;
void addEdge(int u,int v,long long w)
{
	edge[cnt].from=u;
	edge[cnt].to=v;
	edge[cnt].weight=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
 
int dis[1000010];
bool vis[1000010];
priority_queue<node>qp;
void dijkstra(int s){
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[s]=0; vis[s]=true;
	qp.push((node){s,0});
	while(!qp.empty())
	{
		int cntnode=qp.top().id;
		qp.pop(); vis[cntnode]=false;
		
		for(int i=head[cntnode]; i!=-1; i=edge[i].next)
		{
			if(dis[edge[i].to]>dis[cntnode]+edge[i].weight)
			{
				dis[edge[i].to]=dis[cntnode]+edge[i].weight;
				if(!vis[edge[i].to])
				{
					vis[edge[i].to]=true;
					qp.push((node){edge[i].to, dis[edge[i].to]});
				}
			}
		}
	}
}

signed main()
{
	memset(head, -1, sizeof(head));
	memset(dis, 0x7f7f7f7f, sizeof(dis));
	cin>>n>>m>>k>>s>>t;
	for(int i=1,u,v;i<=m;i++)
	{
		long long w;
		cin>>u>>v>>w;
		addEdge(u,v,w);
		addEdge(v,u,w);
		for(int j=1;j<=k;j++)
		{
			addEdge(u+j*n,v+j*n,w);
			addEdge(v+j*n,u+j*n,w);
			addEdge(u+(j-1)*n,v+j*n,0);
			addEdge(v+(j-1)*n,u+j*n,0);
		}
	}
	
	dijkstra(s);
	int ans=0x7f7f7f7f;
	for(int i=0;i<=k;i++)
	{
		ans=min(ans, dis[i*n+t]);
	}
	cout<<ans;
	return 0;
}
2024/10/14 19:29
加载中...