大家都是两遍SPFA吗?我这里就一遍dp啊;
首先判断对于一个点u,是否可以从一号点走到这里,并且可以从u走到n号点; 对于这样的点我们打上标记;
那么抛出水晶球的点一定是从打上标记的点中选出一个;(自己可以理解一下)
然后跑一遍dp,dp[i]表示从点1到点i的若干条路径中,所经过的点的权值最小的值;
比较明显的发现dp[v]可以从dp[u]继承过来(v是u的儿子),所以具有优美的DP性质;
最后ans=max(w[i]-dp[i]);
#include <bits/stdc++.h> #define cin std::ios::sync_with_stdio(false); cin #define cout std::ios::sync_with_stdio(false); cout using namespace std; int n,m; struct littlestar{ int to; int nxt; }star[1000010],star2[1000010]; int head[1000010],cnt,head2[1000010],cnt2; inline void add(int u,int v) { star[++cnt].to=v; star[cnt].nxt=head[u]; head[u]=cnt; } inline void add2(int u,int v) { star2[++cnt].to=v; star2[cnt].nxt=head2[u]; head2[u]=cnt; } int w[1000010]; queue<int> q; int bo1[1000010],bo2[1000010]; void bfs1(int s) { while(q.size()) q.pop(); q.push(s); bo1[s]=1; while(q.size()){ int u=q.front(); q.pop(); for(register int i=head[u];i;i=star[i].nxt){ int v=star[i].to; if(!bo1[v]){ bo1[v]=1; q.push(v); } } } } void bfs2(int s) { while(q.size()) q.pop(); q.push(s); bo2[s]=1; while(q.size()){ int u=q.front(); q.pop(); for(register int i=head2[u];i;i=star2[i].nxt){ int v=star2[i].to; if(!bo2[v]){ bo2[v]=1; q.push(v); } } } } int f[1000010]; int vis[1000010]; void SPFA() { while(q.size()) q.pop(); for(register int i=1;i<=n;i++) f[i]=999999999; q.push(1); f[1]=w[1]; vis[1]=1; while(q.size()){ int u=q.front(); q.pop(); vis[u]=0; for(register int i=head[u];i;i=star[i].nxt){ int v=star[i].to; if(!vis[v]){ vis[v]=1; if(f[v]==999999999){ f[v]=min(f[u],w[v]); q.push(v); } else{ if(f[u]<f[v]){ f[v]=f[u]; q.push(v); } } } } } } int main() { cin>>n>>m; for(register int i=1;i<=n;i++){ cin>>w[i]; } for(register int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; if(w==1){ add(u,v); add2(v,u); } else{ add(u,v); add2(v,u); add(v,u); add2(u,v); } } bfs1(1); bfs2(n); SPFA(); int ans=0; for(register int i=1;i<=n;i++){ if(bo1[i]&&bo2[i]){ ans=max(w[i]-f[i],ans); } } cout<<ans<<endl; }