想越狱的小衫

MYShion · 2025-01-23 21:42:46 · 题解

每组测试数据的第一行有一个正整数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;
    }
}