蒟蒻求助
查看原帖
蒟蒻求助
756180
Not_defined楼主2023/10/27 13:53

不会分层图,请问我这个方法为什么会错,WA两个点。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int M=1e4+10,N=2e3+10;
int k,n,m,cnt,s,t,ans[N],pb[N],head[N];
bool vis[N];
struct node
{
	int next,to,val1,val2;
}e[M<<1];
struct stu
{
	int tot,pos;
	bool operator <(const stu &x)const
	{
		return x.tot<tot;
	}
};
void add(int u,int v,int t,int h)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].val1=t;
	e[cnt].val2=h;
	head[u]=cnt;
}
priority_queue<stu>q;
signed main()
{
	cin>>k>>n>>m;
	memset(ans,inf,sizeof ans);
	for(int i=1;i<=m;i++)
	{
		int u,v,t,h;
		cin>>u>>v>>t>>h;
		add(u,v,t,h),add(v,u,t,h);
	}
	cin>>s>>t;
	ans[s]=0,pb[s]=0;
	q.push((stu){0,s});
	while(!q.empty())
	{
		stu tmp=q.top();q.pop();
		int x=tmp.pos;
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(ans[y]>ans[x]+e[i].val1&&pb[x]+e[i].val2<k)
			{
				ans[y]=ans[x]+e[i].val1;
				pb[y]=pb[x]+e[i].val2;
				if(!vis[y])q.push((stu){ans[y],y});
			}
		}
	}
	if(ans[t]>=inf)puts("-1");
	else cout<<ans[t];
	return 0;
}
2023/10/27 13:53
加载中...