TLE是理所应当的,不过为什么不超时的WA了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int maxn,ans,n,m;
int w[100010],head[100010];
struct node{
int to,nxt;
}edge[100010];
bool vis[100010];
int idx;
void add(int u,int v)
{
edge[++idx].nxt=head[u];
edge[idx].to=v;
head[u]=idx;
}
void dfs(int x,int sum)
{
vis[x]=1;
for(int i=head[x];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(vis[v])
continue;
ans=max(ans,sum+w[v]);
dfs(v,sum+w[v]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
dfs(i,w[i]);
maxn=max(ans,maxn);
ans=0;
}
cout<<maxn;
return 0;
}
10 20
970 369 910 889 470 106 658 659 916 964
3 2
3 6
3 4
9 5
8 3
5 8
9 1
9 7
9 8
7 5
3 7
7 8
1 7
10 2
1 10
4 8
2 6
3 1
3 5
8 5
6911