NC13889. Magic Maze
描述
输入描述
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
示例1
输入:
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=20C++14(g++5.4) 解法, 执行用时: 1516ms, 内存消耗: 35424K, 提交时间: 2019-09-24 00:54:35
#include<bits/stdc++.h>
using namespace std;
struct edge{
int v,w;
};
int dp[1005];
vector<edge>V[1005];
int dfs(int u){
if(dp[u]) return dp[u];
for(int i=0;i<V[u].size();i++){
edge &e=V[u][i];
dp[u]=max(dp[u],dfs(e.v)+e.w);
}
return dp[u];
}
int main(){
int t; cin>>t;
while(t--){
int n,m; cin>>n>>m;
for(int i=0;i<n;i++) V[i].clear(),dp[i]=0;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
V[u].push_back(edge{v,w});
}
int ans=-1e9;
for(int i=0;i<n;i++){
ans=max(ans,dfs(i));
}
cout<<ans<<endl;
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 1193ms, 内存消耗: 4248K, 提交时间: 2022-08-09 20:19:52
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int a[1005][1005];
int dp[1005];
int n,m;
int dfs(int i)
{
if(dp[i]!=0) return dp[i];
for(int j=0;j<n;j++)
{
if(a[i][j]!=inf)
{
dp[i]=max(dp[i],dfs(j)+a[i][j]);
}
}
return dp[i];
}
int main()
{
int t;
cin>>t;
while(t--)
{
memset(dp,0,sizeof(dp));
memset(a,0x3f,sizeof(a));
cin>>n>>m;
int i;
for(i=0;i<m;i++)
{
int u,v,w;
cin>>u>>v>>w;
a[u][v]=w;
}
int ans=0;
for(i=0;i<n;i++)
ans=max(ans,dfs(i));
cout<<ans<<endl;
}
return 0;
}