P3084 [USACO13OPEN]Photo G

又是一个差分约束的题 好像dp也能写

#include
#include
#include
#include
#include
#define Endl endl;//qwq
using namespace std;
const int maxn=1e6;
int n,m,cnt=1;
int head[maxn],vis[maxn],dis[maxn];
struct node
{
	int nxt;
	int to;
	int w;
}edge[maxn];
void add(int x,int y,int z)
{
	edge[cnt].to=y;edge[cnt].w=z;edge[cnt].nxt=head[x];head[x]=cnt++;
}
//int cn[maxn];
int l,r;
int tot=0;
int spfa()
{
	deque q;//双端队列优化spfa
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0;//从0开始的原因见下面
	vis[0]=1;
	q.push_back(0);
	while(q.size())
	{
		int x=q.front();
		q.pop_front();
		vis[x]=0;
		for(int i=head[x];i;i=edge[i].nxt)
		{
			int y=edge[i].to,z=edge[i].w;
			if(dis[y]>dis[x]+z)
			{
				dis[y]=dis[x]+z;
				//cn[y]=cn[x]+1;
				if(!vis[y])
				{
					if(++tot>1926817) return -1;//人要有点信仰，这是梦想spfa的核心部分
					//if(cn[y]>n)return -1;这是正儿八经的判负环，请一定要学会
					vis[y]=1;
					if(q.size()&&dis[y]>dis[q.front()])q.push_back(y);
					else q.push_front(y);
				}
			}
		}
	}
	return dis[n];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>l>>r;
		add(l-1,r,1);
		add(r,l-1,-1);
	}
	for(int i=1;i<=n;i++)
		add(i,i-1,0),add(i-1,i,1);//i-1可能为0，所以上面最短路要从0开始跑（前后呼应~~手动滑稽）
	cout<