1 //Accepted    300 KB    15 ms 2 //dp时用到了a[n+1]可是一直没把她赋值，WA了无数次 3 //dp[i]=max(dp[j]+a[i]) j<i map[j][i]=1 4 #include <cstdio> 5 #include <cstring> 6 #include <iostream> 7 using namespace std; 8 const int imax_n = 105; 9 const int inf = -100000000;10 int map[imax_n][imax_n];11 int dp[imax_n];12 int a[imax_n];13 int pre[imax_n];14 int n,m;15 void Dp()16 {17     for (int i=1;i<=n+1;i++)18     {19         dp[i]=inf;20     }21     dp[1]=0;22     for (int i=2;i<=n+1;i++)23     {24         for (int j=1;j<i;j++)25         if (map[j][i]==1)26         {27             if (dp[i]<dp[j]+a[i])28             dp[i]=dp[j]+a[i],pre[i]=j;29         }30     }31 }32 void output(int x)33 {34     if (x==1)35     {36         printf("1");37         return ;38     }39     output(pre[x]);40     printf("->%d",x);41 }42 int main()43 {44     int T;45     scanf("%d",&T);46     for (int t=1;t<=T;t++)47     {48         scanf("%d",&n);49         for (int i=1;i<=n;i++)50         scanf("%d",&a[i]);51         a[n+1]=0;52         scanf("%d",&m);53         int x,y;54         memset(map,0,sizeof(map));55         for (int i=0;i<m;i++)56         {57             scanf("%d%d",&x,&y);58             map[x][y]=1;59         }60         Dp();61         if (t!=1) printf("\n");62         printf("CASE %d#\n",t);63         printf("points : %d\n",dp[n+1]);64         printf("circuit : ");65         output(pre[n+1]);66         printf("->1\n");67     }68     return 0;69 }

  1 //Accepted    440 KB    0 ms  2 //spfa  3 #include <cstdio>  4 #include <cstring>  5 #include <iostream>  6 #include <queue>  7 #include <string.h>  8 using namespace std;  9 const int imax_n = 201; 10 const int imax_e = imax_n*imax_n; 11 const int inf = -100000000; 12 struct edge 13 { 14     int u,v,c; 15     edge() 16     { 17  18     } 19     edge(int u,int v,int c):u(u),v(v),c(c) 20     { 21  22     } 23 }p[imax_e]; 24  25 int head[imax_n]; 26 int next[imax_e]; 27 int vis[imax_n]; 28 int total_interesting_point[imax_n]; 29 int interesting_point[imax_n]; 30 int e; 31 int n,m; 32  33 void init() 34 { 35     memset(head,-1,sizeof(head)); 36     memset(next,-1,sizeof(next)); 37     memset(vis,0,sizeof(vis)); 38     e=0; 39 } 40 void addEdge(int u,int v,int c) 41 { 42     p[e]=edge(u,v,c); 43     next[e]=head[u]; 44     head[u]=e++; 45 } 46 void outputTrack(int x) 47 { 48     if (x==1) 49     { 50         return ; 51     } 52     for (int i=1;i<=n;i++) 53     if (total_interesting_point[i]+interesting_point[x]==total_interesting_point[x]) 54     { 55         outputTrack(i); 56         printf("%d->",i); 57         return ; 58     } 59 } 60 queue<int > q; 61 void Dp() 62 { 63     for (int i=1;i<=n+1;i++) 64     total_interesting_point[i]=inf; 65     total_interesting_point[1]=0; 66     while (!q.empty()) q.pop(); 67     q.push(1); 68     vis[1]=true; 69     while (!q.empty()) 70     { 71         int x=q.front(); 72         q.pop(); 73         vis[x]=false; 74         for (int i=head[x];i!=-1;i=next[i]) 75         { 76             int nx=p[i].v; 77             if (x<nx && total_interesting_point[nx]<total_interesting_point[x]+interesting_point[nx]) 78             { 79                 total_interesting_point[nx]=total_interesting_point[x]+interesting_point[nx]; 80                 if (!vis[nx]) 81                 { 82                     q.push(nx); 83                     vis[nx]=true; 84                 } 85             } 86         } 87     } 88     printf("points : %d\n",total_interesting_point[n+1]); 89     printf("circuit : "); 90     outputTrack(n+1); 91     printf("1\n"); 92 } 93 int main() 94 { 95     int T; 96     scanf("%d",&T); 97     for (int t=1;t<=T;t++) 98     { 99         scanf("%d",&n);100         for (int i=1;i<=n;i++)101         scanf("%d",&interesting_point[i]);102         interesting_point[n+1]=0;103         init();104         scanf("%d",&m);105         int x,y;106         for (int i=0;i<m;i++)107         {108             scanf("%d%d",&x,&y);109             addEdge(x,y,0);110         }111         if (t!=1) printf("\n");112         printf("CASE %d#\n",t);113         Dp();114     }115     return 0;116 }