蒟蒻求助 75pts
查看原帖
蒟蒻求助 75pts
433518
名字好难取144楼主2021/10/6 11:28

求大佬帮忙看看

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#define ll long long
#define dist dis
using namespace std;
const ll N=5e5+10;

ll p=114623525089379210;

inline ll read()
{
	ll s=0,w=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}

bool vis[N<<2];

ll mess[N<<2],head[N<<2],dis[N<<2];

ll n,m,s,t,g,q,cnt;

struct edge{
	ll to,next,w;   
}e[N<<1];

struct node{
	ll id,w,time;   //节点编号,权值,总花费时间 
}tt;

void add(ll u,ll v,ll w)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].w=w;
	head[u]=cnt;
}

void init_dis()   //手动初始化 
{
	for(int i=0;i<=n;++i) dis[i]=p;
}

void spfa()  //常规spfa 
{
	init_dis();
	queue<node> q;
	q.push( (node) {s,0,0} );
	dis[s]=0;vis[s]=1;
	while(!q.empty())
	{
		tt=q.front(); q.pop();
		ll u=tt.id;
		vis[u]=0;
		if(tt.time>=mess[u]) continue;
		for(ll i=head[u];i;i=e[i].next)
		{
			ll v=e[i].to;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				//vis[v]=1;
				if(!vis[v]) q.push( (node) {v,dis[v],tt.time+dis[v]} ),vis[v]=1;
			}
		}
	}
}



int main()
{
scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&s,&t,&g,&q);
	for(ll i=1,h,l;i<=n;++i)   
	{
		scanf("%lld%lld",&h,&l);
		if(h<=l&&q!=0) mess[i]=ceil((l-h)/q); //mess存储的是节点不可通过的时间 
		else if(h<=l&&q==0) mess[i]=l-h;
		else mess[i]=-1;  //意思是不可以过这个点 
	}
	for(ll i=1,u,v,w;i<=m;++i)
	{
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w); add(v,u,w);
	}
	spfa();
	if(dis[t]==p||dis[t]>=g) cout<<"wtnap wa kotori no oyatsu desu!";
	else cout<<dis[t]<<endl; 
	return 0;
}
2021/10/6 11:28
加载中...