AC_Code:
1 #include <iostream>
2 #include <cstdio>
3 #include <cmath>
4 #include <cstring>
5 #include <cstdlib>
6 #include <string>
7 #include <vector>
8 #include <queue>
9 #include <vector>
10 #include <algorithm>
11 typedef long long ll;
12 const int inf=0x3f3f3f3f;
13 const double pi=acos(-1.0);
14 const int maxn=210;
15 using namespace std;
16
17 int mp[maxn][maxn];
18 int w[maxn],pre[maxn],f[maxn];
19
20 void print(int k){
21 if(k==0) return ;
22 print(pre[k]);
23 if( pre[k]==0 ) printf("%d",k);
24 else printf("-%d",k);
25 }
26
27 int main()
28 {
29 int n;
30 scanf("%d",&n);
31 for(int i=1;i<=n;i++){
32 scanf("%d",&w[i]);
33 f[i]=w[i];
34 }
35 int x,y;
36 while( scanf("%d%d",&x,&y)&&x+y ){
37 mp[x][y]=1;
38 }
39 int maxx=-inf,k;
40 for(int i=1;i<=n;i++){
41 for(int j=1;j<=n;j++){
42 if( mp[j][i]==1 && f[i]<f[j]+w[i] ){
43 f[i]=f[j]+w[i];
44 pre[i]=j;
45 }
46 }
47 if(f[i]>maxx ){
48 maxx=f[i];
49 k=i;
50 }
51 }
52 print(k);
53 printf("\n%d\n",maxx);
54 return 0;
55 }