题目描述

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;
}