[AGC056C] 01 Balanced

差分约束系统，Dijkstra 算法

差分约束系统的常见优化：前缀和。

然后乱搞定义把边权全部变成非负即可。

Code

#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e6+7;
int n,m;
int u,v,w;
int s;
int cnt;
int head[N];
struct edge{
	int to,ne,val;
}e[N<<2]; 
void add(int u,int v,int w) {
	e[++cnt]={v,head[u],w};
	head[u]=cnt;
}
int dis[N];
bool vi[N];
struct node{
	int u,dis;
	bool operator> (const node &b)const{
		return dis>b.dis;
	}
};
priority_queue<node,vector<node>,greater<node> > q;
void getans(){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push({s,dis[s]});
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vi[u]) continue;
//		pf("%d\n",u);
		vi[u]=1;
		for(int i=head[u];i;i=e[i].ne){
			int v=e[i].to,w=e[i].val;
//			pf("%d %d %d\n",i,v,w);
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}
int main(){
	sf("%d%d",&n,&m);
	s=0;
//	for(int i=1;i<=n;i++) add(s,i,0);
	for(int i=1;i<=n;i++) add(i-1,i,1),add(i,i-1,1); 
	for(int i=1;i<=m;i++){
		sf("%d%d",&u,&v);
		u--;
		add(u,v,0),add(v,u,0);
	}
	getans();
//	for(int i=0;i<=n;i++) pf(" %d\n",dis[i]);
	for(int i=1;i<=n;i++){
		if(dis[i]-dis[i-1]>0) pf("0");
		else pf("1");
	}
}