一道类似拓扑排序的思路了
开始直接裸的拓扑，结果TLE死。。。
想了很久，改了个加上了个记忆化，171ms搞定了。。。
#include <stdio.h>
#include <string.h>
struct P
{
int hasfa, haschild, flag;
int child[1010], index[1010];
}data[1010];
int n, m;
int dp[1010];
int max(int a, int b)
{
return a>b?a:b;
}
int dfs(int i)
{
if ( dp[i] )
return dp[i];
if ( data[i].haschild )
{
int maxn= 0;
for ( int j = 0 ; j < data[i].flag ; j++ )
{
int t= dfs(data[i].index[j])+data[i].child[data[i].index[j]];
maxn= max( maxn , t );
}
return dp[i]= maxn;
}
else
return dp[i]=1;
}
int main()
{
while ( EOF != scanf("%d%d", &n, &m) )
{
int i, u, s, t;
memset(data, 0, sizeof(P)*n);
memset(dp, 0, sizeof(dp));
for ( i = 0 ; i < m ; i++ )
{
scanf("%d%d%d", &u, &s, &t);
data[s].hasfa= 1;
data[u].haschild= 1;
data[u].child[s]= t;
data[u].index[data[u].flag++]= s;
}
for ( i = 0 ; i < n ; i++ )
{
if ( !data[i].hasfa )
dp[i]=dfs(i);
}
int maxn= 0;
for ( i = 0 ; i < n ; i++ )
maxn= max(maxn , dp[i]);
printf("%d\n", maxn);
}
return 0;
}