88分玄关求调
查看原帖
88分玄关求调
816777
gengziyang2010楼主2024/10/17 15:24

WA了#5、#6,求大佬调一下

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define int long long
using namespace std;
struct node{
	int v,nxt,t,h;
}a[20010];
int k,n,m,head[2010],tot,s,t,vis[2010],d[2010];
void add(int u,int v,int t,int h){
	a[++tot].v=v;
	a[tot].t=t;
	a[tot].h=h;
	a[tot].nxt=head[u];
	head[u]=tot;
}
priority_queue<pair<int,pair<int,int> > > q;
signed main(){
	memset(d,0x7f,sizeof(d));
	scanf("%lld%lld%lld",&k,&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,t,h;
		scanf("%lld%lld%lld%lld",&u,&v,&t,&h);
		add(u,v,t,h);
		add(v,u,t,h);
	}
	scanf("%lld%lld",&s,&t);
	q.push(make_pair(0,make_pair(s,k)));
	d[s]=0;
	while(!q.empty()){
		int x=q.top().second.first;
		int c=q.top().second.second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=a[i].nxt){
			int y=a[i].v;
			int z=a[i].t;
			int h=a[i].h;
			if(d[y]>d[x]+z&&c>h){
				d[y]=d[x]+z;
				q.push(make_pair(-d[y],make_pair(y,c-h)));
			}
		}
	}
	if(d[t]==0x7f7f7f7f7f7f7f7f) printf("-1");
	else printf("%lld",d[t]);
	return 0;
}
2024/10/17 15:24
加载中...