Vijos 1391 想越獄的小杉

題目位置

https://vijos.org/p/1391

題目描述

小杉看了看自己的紋身，明白了整個管道網是由N個小房間和若幹小房間之間的單向的管道組成的。

小房間編号為不超過N的正整數。

對于某個管道，小杉隻能在人品不超過一定程度時通過。

小杉一開始在房間1，現在小杉想知道，每個小房間他最多能夠以人品多少的狀态到達。

注意，小杉的人品在出發以後是不會改變的。

輸入格式

每組測試資料的

第一行有一個正整數N(1<=N<=2000)。

接下來若幹行描述管道，每行三個正整數A,B,R(1<=A,B<=N)，表示A房間有一條到達B房間的管道，且小杉的人品不超過R時可以通過（注意從B房間不可由此管道到達A房間，即管道是單向的)

整個輸入資料以一行0 0 0結束

特别地，對于30%的資料，有N<=100

輸出格式

對每組測試資料輸出N-1行，分别表示對于2到N号的小房間，小杉最多能夠以人品多少的狀态到達。

樣例輸入

4

1 2 30

1 3 20

2 3 25

3 4 30

2 4 20

0 0 0

樣例輸出

30

25

25

樣例圖示

對于這道題，有幾點比較坑人，解決了這幾點後就沒什麼難的了：

首先，題目告訴我們他可能為多組資料，要進行判斷，

其次，如果到不了的話要輸出0，這也是暴零的原因。

然後結合圖分析後發現，這隻是一道最短路的題目，隻不過判斷的是前面邊的最小值與新加邊二者的最小值，這樣就可以得出代碼了

C++代碼

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n,tot,to[],nex[],val[],head[];
int f[],v[];
queue <int> q;
void add(int x,int y,int z)
{
    to[++tot]=y;
    val[tot]=z;
    nex[tot]=head[x];
    head[x]=tot;
}
void spfa()
{
    int x,y;
    memset(f,,sizeof(f));
    q.push(),f[]=,v[]=;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        v[x]=;
        for(int i=head[x];i;i=nex[i])
        {
        if(f[y=to[i]]<min(f[x],val[i]))//比較源點與入度，較小者關系
            {
                f[y]=min(f[x],val[i]);
                if(!v[y])
                {
                  v[y]=;
                  q.push(y);
                }
            }
        }
    }
    for(int i=;i<=n;i++)
        printf("%d\n",f[i]);//輸出
}
int main()
{
    while(~scanf("%d",&n))//判斷多組資料
    {
        int a,b,c,x,y;
        memset(head,,sizeof(head));
        tot=;//記得置零
        while(scanf("%d%d%d",&a,&b,&c)&&!(a==&&b==&&c==))
            add(a,b,c);

        spfa();
    }
    return ;
}
           

即可AC

題目傳送門

https://vijos.org/p/1391