先有了这个讨论:
好想法!看到并没有人写,于是有了这篇题解。
按照思路,先预处理出起点和终点所能扩展到的点集,记为isCsn[]
,然后将这个数组中所有的点全部入堆,按照 dijkstra 的方法进行更新,这样每个点第一次出堆时便是最优答案,且保证了每个点只会被扩展一次,复杂度也就能严格 $O(m\log n)$ 了。(虽然这道题没卡
然而我的实现很丑,常数较大,实际表现还是被 SPFA 爆踩 orz(STL 效率一言难尽)。
放上可有可无的代码:
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+5,M=5e5+5;
struct Edge{int to,nxt;}e[M<<2];
int head[N],invhead[N],w[N],f[N],g[N];
int cnt,n,m,ans;
bool vis[N],isCsn[N];
inline void add(int h[],int u,int v) {e[++cnt]=(Edge){v,h[u]},h[u]=cnt;}
void dfs(int h[],int u)
{
isCsn[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
if(isCsn[e[i].to]) continue;
dfs(h,e[i].to);
}
}
void dijkstra(int h[],int d[],bool type)
{
priority_queue<pii> q;
for(int i=1;i<=n;++i)
if(isCsn[i])
q.push({type?-w[i]:w[i],i}),d[i]=w[i];
while(!q.empty())
{
int now=q.top().second; q.pop();
if(vis[now]) continue;
vis[now]=1;
for(int i=h[now],v;i;i=e[i].nxt)
{
v=e[i].to;
if(type&&d[v]>min(d[now],w[v])||!type&&d[v]<max(d[now],w[v]))
{
if(type) d[v]=min(d[now],w[v]);
else d[v]=max(d[now],w[v]);
q.push({type?-d[v]:d[v],v});
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&w[i]);
for(int i=1,a,b,c;i<=m;++i)
{
scanf("%d%d%d",&a,&b,&c);
add(head,a,b); add(invhead,b,a);
if(c==2) add(head,b,a),add(invhead,a,b);
}
memset(f,0x3f,sizeof(f));
dfs(head,1); dijkstra(head,f,1);
memset(isCsn,0,sizeof(isCsn));
memset(vis,0,sizeof(vis));
dfs(invhead,n); dijkstra(invhead,g,0);
for(int i=1;i<=n;++i) ans=max(ans,g[i]-f[i]);
printf("%d",ans);
return 0;
}