首先一个点能否选择的条件是 \(dis_{1,x}+dis_{x,n}=dis_{1,n}\)
正解是计算一条道路上的所有为 \(-1\) 边的选择范围,是个一次函数。
但是有一种做法,枚举所有的存在的边权,可以证明若 \(-1\) 边的边权为两个存在的边权之间,那么它的情况一定可以被大的和小的共同覆盖。
\(spfa\) 即可
Code:
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf,OPUT[100];
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++;
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(!isdigit(ch)) {if (ch=='-') f=0;ch=gc();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
template<typename T>inline void print(T x,char t) {
if (x<0) putchar('-'),x=-x;
if (!x) return putchar('0'),(void)putchar(t);
ri cnt(0);
while(x) OPUT[p(cnt)]=x%10,x/=10;
for (ri i(cnt);i;--i) putchar(OPUT[i]^48);
return (void)putchar(t);
}
}
using IO::read;using IO::print;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=1e3+7,INF=1061109567;
map<int,int> mp;
int first[N],wai[N<<1],que[N*100],vis[N],ans[N],W,tot,t=1,n,m;
struct edge{int v,w,nxt;}e[N<<2];
ll disf[N],disr[N];
inline void add(int u,int v,int w) {
e[t].v=v,e[t].w=w,e[t].nxt=first[u],first[u]=t++;
e[t].v=u,e[t].w=w,e[t].nxt=first[v],first[v]=t++;
}
inline void spfaf() {
memset(disf,127,sizeof(ll)*(n+1));
ri hd=1,tl=0;
int x=1;
disf[que[p(tl)]=x]=0;
while(hd<=tl) {
vis[x=que[hd++]]=0;
for (ri i(first[x]),v;i;i=e[i].nxt) {
int w=(e[i].w==-1)?W:e[i].w;
if (disf[v=e[i].v]>disf[x]+w) {
disf[v]=disf[x]+w;
if (!vis[v]) vis[que[p(tl)]=v]=1;
}
}
}
}
inline void spfar() {
memset(disr,127,sizeof(ll)*(n+1));
ri hd=1,tl=0;
int x=n;
disr[que[p(tl)]=x]=0;
while(hd<=tl) {
vis[x=que[hd++]]=0;
for (ri i(first[x]),v;i;i=e[i].nxt) {
int w=(e[i].w==-1)?W:e[i].w;
if (disr[v=e[i].v]>disr[x]+w) {
disr[v]=disr[x]+w;
if (!vis[v]) vis[que[p(tl)]=v]=1;
}
}
}
}
inline void solve(int w) {
W=w;
spfaf(),spfar();
for (ri i(1);i<=n;p(i)) if (disf[i]+disr[i]==disf[n]) ans[i]=1;
}
inline int main() {
//FI=freopen("nanfeng.in","r",stdin);
//FO=freopen("nanfeng.out","w",stdout);
read(n),read(m);
for (ri i(1),u,v,w;i<=m;p(i)) {
read(u),read(v),read(w);
if (w!=-1&&mp.find(w)==mp.end()) mp[wai[p(tot)]=w]=1;
add(u,v,w);
}
if (mp.find(0)==mp.end()) wai[p(tot)]=0;
wai[p(tot)]=INF;
for (ri i(1);i<=tot;p(i)) solve(wai[i]);
for (ri i(1);i<=n;p(i)) putchar(ans[i]^48);
puts("");
return 0;
}
}
int main() {return nanfeng::main();}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章