Codevs 4019 想越狱的小明

4019 想越狱的小明

时间限制: 1 s

空间限制: 1000 KB

题目等级 : 钻石 Diamond

题目描述 Description

这次小明来到了经典美剧《越狱》的场景里……

它被抓起来了（-.-干嘛幻想这么郁闷的场景……）。

小明身为新一代的Scofield，在挖了半个月之后终于挖通牢房里的地道。

在地道里，无数的管道路线困惑了它。（若对情节有任何疑问，请观看原剧）

小明看了看自己的纹身，明白了整个管道网是由N个小房间和若干小房间之间的单向的管道组成的。

小房间编号为不超过N的正整数。

对于某个管道，小明只能在人品不超过一定程度时通过。

小明一开始在房间1，现在小明想知道，每个小房间他最多能够以人品多少的状态到达。

注意，小明的人品在出发以后是不会改变的。

输入描述 Input Description

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

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

即管道是单向的)

整个输入数据以一行0 0 0结束

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

表示A房间有一条到达B房间的管道，且小明的人品不超过R时可以通过（注意从B房间不可由此管道到达A房间，

输出描述 Output Description

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

样例输入 Sample Input

4

1 2 30

1 3 20

2 3 25

3 4 30

2 4 20

0 0 0

样例输出 Sample Output

30

25

25

数据范围及提示 Data Size & Hint

1s

小明最多能够在人品为30的情况下到达小房间2(1->2)

小明最多能够在人品为25的情况下到达小房间3(1->2->3)

小明最多能够在人品为25的情况下到达小房间4(1->2->3->4)；

/*

    Name: Codevs 4019

    Copyright: yes.

    Author: nancheng58

    Date: 15-10-16 15:28

    Description:

    询问边权路径最大路径的最小值.

    这题不用最大树+lca直接spfa暴力就好了.

    dis[i]表示到i点的最大值.

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define MAXN 2001

using namespace std;

int head[MAXN],dis[MAXN],n,m,cut;

struct data{int v,next,x;}e[MAXN*MAXN];

bool b[MAXN];

queue<int>q;

void add(int u,int v,int z)

{

    e[++cut].v=v;

    e[cut].x=z;

    e[cut].next=head[u];

    head[u]=cut;

}

int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;if(ch==EOF) return -1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

    return x*f;

}

void spfa()

{

    memset(dis,0,sizeof dis);

    dis[1]=1e9;

    q.push(1);

    while(!q.empty())

    {

        int u=q.front();q.pop();b[u]=false;

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;

            if(dis[v]<min(dis[u],e[i].x)) {

                dis[v]=min(dis[u],e[i].x);

                if(!b[v]) b[v]=true,q.push(v);

            }

        }

    }

}

int main()

{

    int x,y,z;

    while((n=read())!=-1)

    {

        while(true)

        {

            x=read(),y=read(),z=read();

            if(!x&&!y&&!z) break;

            add(x,y,z);

        }

        spfa();

        for(int i=2;i<=n;i++) printf("%d\n",dis[i]);

        cut=0;memset(head,0,sizeof head);

    }

    return 0;

}

巴特西

Codevs 4019 想越狱的小明

最新文章

热门文章