spfa四tle三wa怎么改?
  • 板块P1119 灾后重建
  • 楼主烛木
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/9/1 20:24
  • 上次更新2023/11/5 13:50:32
查看原帖
spfa四tle三wa怎么改?
366746
烛木楼主2020/9/1 20:24

spfa四tle三wa怎么改?

#include<iostream>
#include<cstdio>
#define il inline
using namespace std;
int tot,head,tail,n,m,Q,x,y,t,q[202],team[202],vis[202],dis[202];
struct node
{
	int first,next,go,distance;
}p[40000];
il int star(int a,int b,int c)
{
	p[++tot].next=p[a].first;
	p[a].first=tot;
	p[tot].go=b;
	p[tot].distance=c;
}
il void spfa(int a)
{
	for(int i=0;i<n;i++)
	{
		dis[i]=0x7fffffff;
		vis[i]=0;
	}
	if(q[a]>t) return; 
	head=tail=dis[a]=0;
	team[++tail]=a;
	while(head<=tail)
	{
		int x=team[++head];
		vis[x]=0;
		for(int i=p[x].first;i;i=p[i].next)
	  	{
			int z=p[i].go;
			if(q[z]>t)
			continue;
			if(dis[x]+p[i].distance<dis[z])
			{
				dis[z]=dis[x]+p[i].distance;
				if(!vis[z])
				{
					team[++tail]=z;
					vis[z]=1;
				}
			}
		}
	}
}
il long long read() 
{
    long long x=0,f=1;
    char c=getchar();
    while (c<'0'||'9'<c)
	{
        if (c=='-') f=-1;
        c=getchar();
    }
    while ('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		q[i]=read();
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		x=read();y=read();z=read();
		star(x,y,z);
		star(y,x,z);
	}
	cin>>Q;
	for(int i=1;i<=Q;i++)
	{
		x=read();y=read();t=read();
		if(q[x]>t||q[y]>t)
		cout<<"-1"<<endl;
		else
		{
			spfa(x);
			if(dis[y]==0x7fffffff)
			cout<<"-1"<<endl;
			else
			cout<<dis[y]<<endl;
		}
	}
	return 0;
}
2020/9/1 20:24
加载中...