題意這樣的：一個(gè)無向圖，一個(gè)員工從a走到b，每點(diǎn)都有一個(gè)權(quán)值，可能為正或者負(fù)，要求給出一條路徑，使得到b以后經(jīng)過權(quán)值和最大。
還是用神通廣大的SPFA，當(dāng)求最長路來辦- -貼代碼
1 # include <cstdio>
2 # include <cstring>
3 using namespace std;
4 # define N 100005
5 # define M 1000005
6 # define max(a,b) ((a)>(b)?(a):(b))
7 int g[N],v[M],nxt[M],c,val[N],q[N],s,e,n,m,id[N],od[N];
8 int dp[N];
9 int main()
10 {
11 while(scanf("%d%d",&n,&m)!=EOF)
12 {
13 memset(g,-1,sizeof(g));
14 c=0;
15 s=e=-1;
16 memset(id,0,sizeof(id));
17 memset(od,0,sizeof(od));
18 for(int i=1;i<=n;i++)
19 dp[i]=-0xfffffff;
20 for(int i=1;i<=n;i++)
21 scanf("%d",val+i);
22 while(m--)
23 {
24 int a,b;
25 scanf("%d%d",&a,&b);
26 v[c]=b;
27 nxt[c]=g[a];
28 g[a]=c++;
29 od[a]++;
30 id[b]++;
31 }
32 for(int i=1;i<=n;i++)
33 if(!id[i])
34 {
35 dp[i]=val[i];
36 q[++e]=i;
37 }
38 int res=-0xfffffff;
39 while(s!=e)
40 {
41 int top=q[++s];
42 if(!od[top])
43 res=max(res,dp[top]);
44 for(int p=g[top];p!=-1;p=nxt[p])
45 {
46 dp[v[p]]=max(dp[v[p]],dp[top]+val[v[p]]);
47 id[v[p]]--;
48 if(!id[v[p]])
49 q[++e]=v[p];
50 }
51 }
52
53 printf("%d\n",res);
54 }
55 return 0;
56 }
57