想越狱的小衫

每组测试数据的第一行有一个正整数N(1<=N<=2000)。

接下来若干行描述管道，每行三个正整数A,B,R(1<=A,B<=N)，表示A房间有一条到达B房间的管道，且小杉的人品不超过R时可以通过（注意从B房间不可由此管道到达A房间，即管道是单向的) 整个输入数据以一行0 0 0结束

特别地，对于30%的数据，有N<=100，对于100%的数据，有N<=2000.

Output Format 对每组测试数据输出N-1行，分别表示对于2到N号的小房间，小杉最多能够以人品多少的状态到达。

重点是最多能够以人品多少的状态，相当于路中最小值的最大值 因此主要式子为dis[i]<min(dis[k],tu[k][i]) 然后的话，这种做法的主要难度在于考虑其他变量的初始值 比如dis[1]的初始值不可以赋成0，同时tu[k][i]也同理，因为若是为1，第一次出队中dis[k]的值为0，会导致其他的所有值也会赋为0，并且要给dis[i]赋值，所以要保证dis[i]的初始值要为0 (若为inf可以想到，dis[i]无论如何不会被赋值) 代码如下

using namespace std;
#define int long long 
#define maxx 10000000
#define N 200001
int m,n,c;
int cnt=0,flag[N]={0};

struct edge{
	int to,w,next=0;
};
edge e[N];
int dis[2002]={0},tu[2002][2002]={maxx};//注意，赋大的值是为了让他尽量可以不被在min()中被选择
queue<int>q;

void spfa(int x)
{
	dis[x]=maxx; //注意，赋大的值是为了让他尽量可以不被在min()中被选择
	q.push(x);
	flag[x]=1;
	int k;
	while(!q.empty())
	{
		k=q.front();						
		for(int i=1;i<=n;i++)				
		{                                //dis[i]=max(dis[k],min(dis[k],tu[k][i]))
		
			if(tu[k][i]!=maxx&&dis[i]<min(dis[k],tu[k][i])) //dis[k]由于是在队首，所以不可能是空值（0）；
			{	
				dis[i]=min(dis[k],tu[k][i]);
				if(!flag[i])
				{
					q.push(i);
					flag[i]=1;
				}
			}
		}
		flag[q.front()]=0;
		q.pop();
	}
}
int a,b,w;
signed main(){
	cin>>n;
	while(cin>>a)
	{
		if(a==0)
		{
			cin>>b>>w;
			break;
		}
		else
		{
			cin>>b>>w;
			tu[a][b]=w;
		}
	}
	for(int i=1;i<=n;i++)
	{
		dis[i]=0; 注意，赋小的值是为了让他尽量可以不被在dis[i]<min()中被选择(比min()小)
		flag[i]=0;
	}
	spfa(1);
	for(int i=2;i<=n;i++)
	{
		cout<<dis[i]<<endl;
	}
}

文章操作

相关推荐

评论

想越狱的小衫