问题标题: 酷町堂：2371 列车路线(train)

2371   列车路线(train)

经验值：1600 时间限制：1000毫秒

安徽省2018年信息学竞赛试题(小学组)

不许抄袭，一旦发现，直接清空经验！

题目描述 Description

终于,卡卡西来到了一个叫“比特兰”的国家,“比特兰”是个很发达的国家, 有着非常高科技的列车,和非常复杂的列车线路。具体来说,从理论上,我们可 以假设这个国家的高科技列车可以不消耗时间的从 A 地瞬间转移到 B 地。同时, 铁路线路复杂到,每对城市之间都有列车连接。但是不幸的是,由于这种列车运 行需要很**护工作,所以每天只能发出一次。从 i 到 j 的列车(i≠j)会在 ti,j 时间发出(保证 ti,j 两两不同)。
如果有一条路径链接A和B两个城市,并且满足路径上的每一条边的发车时间单调递增(也就是说经过的每段铁路的发出时间都要大于上一段的,因为我们 需要从上一段铁路换乘下一段铁路)。 现在“比特兰”的铁路局想要知道,一天
之内,对于每一对i和j,如果想要从i到达j,最早多早能到达呢?

输入描述 Input Description

第1行是一个整数n，接下来n行，每行n个数表示tij（i=j，tij=t0）

输出描述 Output Description

n行，每行n个数表示i到j最早的到达时间。

样例输入 Sample Input

3

0 4 5

2 0 3

1 6 0

样例输出 Sample Output

0 4 5

2 0 3

1 4 0

数据范围及提示 Data Size & Hint

对于 20%的数据,n<=10
对于 40%的数据,n<=20
对于 60%的数据,n<=50
对于 100%的数据,n<=500, ti,j<=10^9

/*
搜索过程
    int h=0,t=1;
    memset(b,0x3f,sizeof(b));
    p[1]=pos,m[1]=0;
    do
    {
        h++;
        for(int i=1;i<=n;i++)
        {
            if(i!=p[h]&&a[p[h]][i]>=m[h]&&b[i]>a[p[h]][i])
            {
                p[++t]=a[i];
                m[t]=b[i]=a[p[h]][i];
                ans[pos][i]=min(ans[pos][i],m[t]);
            }
        }
    }while(h<t);
*/
#include <bits/stdc++.h>
#define maxn1 505
#define maxn2 250005
using namespace std;
int n,a[maxn1][maxn1],ans[maxn1][maxn1],b[maxn1],p[maxn2],m[maxn2];
void search(int pos)
{
    int h=0,t=1;
    memset(b,0x3f,sizeof(b));
    p[1]=pos,m[1]=0;
    do
    {
        h++;
        for(int i=1;i<=n;i++)
        {
            if(i!=p[h]&&a[p[h]][i]>=m[h]&&b[i]>a[p[h]][i])
            {
                p[++t]=i;
                m[t]=b[i]=a[p[h]][i];
                ans[pos][i]=min(ans[pos][i],m[t]);
            }
        }
    }while(h<t);
    return ;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    memset(ans,0x3f,sizeof(ans));
    for(int i=1;i<=n;i++)
    {
        search(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(ans[i][j]!=0x3f3f3f3f&&i!=j)printf("%d ",ans[i][j]);
            else printf("0 ");
        }
        printf("\n");
    }
    return 0;
}

TLE 60分！

求大佬帮忙！