Analysis
建图+强连通分量+SPFA求最长路
但要保证最后到达的点中包含酒馆
虽然思路并不难想，但要求的代码能力很高。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define maxn 500010
using namespace std;
inline int read()
{
int x=;
bool f=;
char c=getchar();
for(; !isdigit(c); c=getchar()) if(c=='-') f=;
for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';
if(f) return x;
return -x;
}
inline void write(int x)
{
if(x<){putchar('-');x=-x;}
if(x>)write(x/);
putchar(x%+'');
}
struct node
{
int from,to,val,nex;
}edge[*maxn];
int n,m,s,p,cnt,ans,top,inl,num;
int x[maxn],y[maxn],head[maxn],dfn[maxn],low[maxn],st[maxn],inn[maxn],sum[maxn],si[maxn],money[maxn],dis[maxn];
bool book[maxn],book1[maxn],bar[maxn];
inline void clear()
{
cnt=;
memset(edge,,sizeof(edge));
memset(head,,sizeof(head));
}
inline void add(int x,int y)
{
cnt++;
edge[cnt].to=y;
edge[cnt].nex=head[x];
head[x]=cnt;
}
inline void build(int x,int y,int z)
{
cnt++;
edge[cnt].from=x;
edge[cnt].to=y;
edge[cnt].val=z;
edge[cnt].nex=head[x];
head[x]=cnt;
}
inline void Tarjan(int u)
{
dfn[u]=low[u]=++num;
st[++top]=u;
for(int i=head[u];i;i=edge[i].nex)
{
int v=edge[i].to;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(!inn[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
inn[u]=++inl;
while(st[top]!=u)
{
if(bar[st[top]])book1[inl]=;
sum[inl]+=money[st[top]];
inn[st[top]]=inl;
--top;
}
if(bar[st[top]])book1[inl]=;
sum[inl]+=money[st[top]];
--top;
}
}
inline void spfa()
{
memset(book,,sizeof(book));
for(int i=;i<=n;i++) dis[i]=;
queue<int> q;
q.push(inn[s]);
book[inn[s]]=;
dis[inn[s]]=sum[inn[s]];
while(!q.empty())
{
for(int i=head[q.front()];i;i=edge[i].nex)
{
if(dis[edge[i].to]<dis[edge[i].from]+edge[i].val)
{
dis[edge[i].to]=dis[edge[i].from]+edge[i].val;
if(book[edge[i].to]==)
{
q.push(edge[i].to);
book[edge[i].to]=;
}
}
}
book[q.front()]=;
q.pop();
}
}
int main()
{
n=read();m=read();
for(int i=;i<=m;i++)
{
x[i]=read();y[i]=read();
add(x[i],y[i]);
}
for(int i=;i<=n;i++)money[i]=read();
s=read();p=read(); for(int i=;i<=p;i++)
{
int x;
x=read();
bar[x]=;
}
for(int i=;i<=n;i++)
if(!dfn[i])
Tarjan(i); clear();
for(int i=;i<=m;i++)
if(inn[x[i]]!=inn[y[i]])
build(inn[x[i]],inn[y[i]],sum[inn[y[i]]]);
spfa();
for(int i=;i<=inl;i++)
if(book1[i]==)
ans=max(ans,dis[i]);
write(ans);
return ;
}
请各位大佬斧正