The first line: the number of case T (1≤T≤110 )
In each test case:
The first line is two integers: the number of resting area n, the number of roads m(1≤n≤1000, 0≤m≤n×(n−1)÷2) m lines follow, each with three integers: the beginning u, the end v, treasure w(0≤u<n,0≤v<n,−1000≤w≤1000)
T lines, each with an integer what is the maximum treasure
2 5 4 0 1 -10 1 2 10 2 3 10 3 4 -10 4 4 0 1 4 0 2 5 2 3 -2 3 1 4
20 7
In the first example, you can go 1 ->2 >3, then the ans is 10+10=20
In the second example, you can go 0 ->2 ->3>-1, then the ans is 5−2+4=7
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1005,INF=999999999;
int G[maxn][maxn],dp[maxn];
int d(int);
int T,i,j,n,m,a,b,c;
int main(){
//freopen("input.txt","r",stdin);
for(scanf("%d",&T);T--;){
for(i=0;i<maxn;i++)
for(j=0;j<maxn;j++) G[i][j]=INF;
for(i=0;i<maxn;i++) dp[i]=INF;
for(scanf("%d%d",&n,&m),i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
G[a][b]=c;
}
int Max=-INF;
for(i=0;i<n;i++) Max=max(Max,d(i));
printf("%d\n",Max);
}
}
int d(int x){
if(dp[x]!=INF) return dp[x];
dp[x]=0;
for(int i=0;i<n;i++)
if(G[x][i]!=INF)
dp[x]=max(dp[x],d(i)+G[x][i]);
return dp[x];
}//记忆搜索
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
