这道题是个Tarjan+DAG上求最长路的好题啊……来说说我的智障做法。
首先这题很明显要缩点，这都没啥，然后我发现要求最长路？
好啊，直接找昨天学的那种，深搜！过了样例就交。
算法一，期望得分100，实际得分7.
？？？好的，发现这个算的是从一个点出发的最长路，我们要求的是终点还必须是酒馆的一条路径，于是乎有了算法二：从每个点倒着往回跑最长路，遇到出发点就停！
算法二，期望得分100，实际得分87.（好吧其实是没卡我）
仔细想了一下发现，好像反着跑的话你可以一直不经过起点，这样不符合要求……
然后想了一下，就又有了算法三：先在正图上把所以起点能到的点都跑出来，这些之中的点再往回跑！
算法三：期望得分100，实际得分75.（？？？？？）
好吧后来发现，这样反着往回跑的话，你还是有可能不经过起点。
于是乎最后只好直接用SPFA跑最长路了……这次终于得到了期望的100分……
看一下代码。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 5000005; const int N = 10000005; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >='0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to,from,v; }e[M],e1[M]; int head[M],dis[M],n,m,ecnt,ecnt1,low[M],dfn[M],idx,cnt,val[M],sval[M],maxn,x,y,s,p,belong[M]; int stack[M],top,head1[M]; bool bar[M],bar1[M],vis[M],pd[M]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].from = x; e[ecnt].next = head[x]; head[x] = ecnt; } void add1(int x,int y,int z) { e1[++ecnt1].to = y; e1[ecnt1].from = x; e1[ecnt1].v = z; e1[ecnt1].next = head1[x]; head1[x] = ecnt1; } void tarjan(int x) { low[x] = dfn[x] = ++idx; vis[x] = 1,stack[++top] = x; for(int i = head[x];i;i = e[i].next) { if(!dfn[e[i].to]) tarjan(e[i].to),low[x] = min(low[x],low[e[i].to]); else if(vis[e[i].to]) low[x] = min(low[x],dfn[e[i].to]); } if(dfn[x] == low[x]) { cnt++; int p; while((p = stack[top--])) { belong[p] = cnt,vis[p] = 0; sval[cnt] += val[p]; if(bar[p]) bar1[cnt] = 1; if(p == x) break; } } } void rebuild() { add1(0,belong[s],sval[belong[s]]); rep(i,1,ecnt) { int r1 = belong[e[i].from],r2 = belong[e[i].to]; if(r1 != r2) add1(r1,r2,sval[r2]); } } void spfa() { queue <int> q; dis[0] = 0,q.push(0); while(!q.empty()) { int k = q.front();q.pop();vis[k] = 0; for(int i = head1[k];i;i = e1[i].next) { if(dis[e1[i].to] < dis[k] + e1[i].v) { dis[e1[i].to] = dis[k] + e1[i].v; if(!vis[e1[i].to]) vis[e1[i].to] = 1,q.push(e1[i].to); } } } } int main() { n = read(),m = read(); rep(i,1,m) x = read(),y = read(),add(x,y); rep(i,1,n) val[i] = read(); s = read(); rep(i,1,n) if(!dfn[i]) tarjan(i); rebuild(); spfa(); p = read(); rep(i,1,p) x = read(),maxn = max(maxn,dis[belong[x]]); printf("%d ",maxn); return 0; }