【2016.10.5NOIP普及模拟】zy的秘密

发布于 2019-04-10  6 次阅读


题目描述

zy和wd是宿舍里的一对活宝,两个人总是吵架,今天,他们又吵架了。wd威胁要把zy和某个mm的故事传出去。zy需要防止自己的秘密暴露,他要安排对策,但是,他不知道wd把秘密传出去后最少多久全班都会知道。由于lsn是团支书而且熟悉班上每一个人,他给了zy一张表,里面有班里所有的朋友关系,并且对于每对朋友,lsn给出了一个数字表示这对朋友中一个知道zy的秘密后最少多少时间另一个也会知道。不过,对于这么多关系,程序设计只拿了B+的zy实在没有办法了,于是他找到了宿舍里的最后一个成员kk。现在,kk把这个光荣而伟大的任务交给了你,你需要告诉kk在wd传出消息最少多少时间后全班都会知道zy的秘密。

输入

第一行一个整数n表示班级的人数。
第二行一个整数m表示lsn提供的关系数。
第3至(2+m)行每行三个整数ai,bi,ci,ai、bi表示ai号与bi号同学是一对朋友,ci为这对朋友中一个知道zy的秘密后另一个也知道的最短时间。wd的编号固定为1号。

输出

一行一个整数表示在wd传出消息多少时间后全班都会知道zy的秘密。如果全班中有人永远不会知道zy的秘密,那么则输出让那些能知道zy秘密的人全知道的最短时间。

思路

其实这题正解是spfa,但是我用了神奇的dp,一直做,做10次的dp就可以过了。。。

#include 
using namespace std;
int f[1005],a[1005],l[1005][1005],xx[1005][1005];
int n,m,x,y,s,ans,z;
int min(int x,int y)
{
    return xy?x:y;
}
int main()
{
    freopen("secret.in", "r", stdin);
    freopen("secret.out", "w", stdout);
    scanf("%d%d",&n,&m);
    for (int i=2;i<=n;i++)
        a[i]=0xfffffff;
    for (int i=1;i<=1000;i++)
        for (int j=1;j<=1000;j++)
            l[i][j]=0x7fffffff;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        l[x][y]=min(l[x][y],z);
        l[y][x]=min(l[y][x],z);
        xx[x][y]=1;
        xx[y][x]=1;
    }
    f[1]=1;
    for (int k=1;k<=10;k++)
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (xx[i][j]==1&&f[i]==1)
            {
                a[j]=min(a[j],a[i]+l[i][j]);
                f[j]=1;
            }
    for (int i=1;i<=n;i++)
        if (f[i]==1)
        {
            ans=max(ans,a[i]);
        }

    printf("%d\n",ans);
    return 0;
}
]]>