关于spfa,它死了
于是我介绍一下稳定$O(mlogn)$的Dij做法
首先,这题不能直接使用Dij是因为图中存在负权边,不符合Dij的性质.
考虑到所有点的水晶球价格不超过100,也就是边权不超过100,不妨将跨层的边都加上1000,从而所有边权都是非负数.
由于只会经过两条跨层的边,最后的结果减去2000即可.
(应该不会被hack吧..)
//Wan Hong 3.0
//notebook
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include <deque>
#include <queue>
typedef int ll;
typedef std::pair<ll,ll> pll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#define MAXN 100011*3
#define KEY 1000
#define MAXM (500011*3)
struct Edge
{
ll v,w,nxt;
}e[MAXM<<1|1];
ll cnt=0,last[MAXN];
void adde(ll u,ll v,ll w)
{
++cnt;
e[cnt].v=v;e[cnt].w=w;
e[cnt].nxt=last[u];last[u]=cnt;
}
struct node
{
ll u,dis;
node(){}
node(ll _u,ll _dis)
{
u=_u,dis=_dis;
}
bool operator <(const node& t)
const
{
return dis>t.dis;
}
};
std::priority_queue<node>q;
ll a[MAXN],dis[MAXN];
void Dij()
{
memset(dis,0x3f,sizeof dis);
q.push(node(1,0));
dis[1]=0;
while(!q.empty())
{
ll u=q.top().u,tmp=q.top().dis;q.pop();
if(dis[u]!=tmp)continue;
for(ll i=last[u];i;i=e[i].nxt)
{
ll v=e[i].v;
if(umin(dis[v],dis[u]+e[i].w))
{
q.push(node(v,dis[v]));
}
}
}
}
int main()
{
ll n=read(),m=read();
for(ll i=1;i<=n;++i)a[i]=read();
for(ll i=1;i<=m;++i)
{
ll u=read(),v=read(),k=read();
adde(u,v,0),adde(u+n,v+n,0),adde(u+n+n,v+n+n,0);
if(k==2)adde(v,u,0),adde(v+n,u+n,0),adde(v+n+n,u+n+n,0);
adde(u,v+n,a[u]+KEY),adde(u+n,v+n+n,-a[u]+KEY);
if(k==2)adde(v,u+n,a[v]+KEY),adde(v+n,u+n+n,-a[v]+KEY);
}
Dij();
//printf("%d",dis[n*3]);
printf("%d",max(-dis[n*3]+2*KEY,0));
return 0;
}
牛逼