感谢楼下的提醒...构好图一定不会交叉，那么用差分约束系统
记得边表开大点，我开了400W才A掉...太菜了
```c++
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct Edge {
int u, v, w;
} edge[4000010];

int N, K, H, R, B;
queue<int> Q;
int d[40010], inq[40010];
vector<int> G[40010];

inline void addEdge(int a, int b, int c) {
edge[B].u = a, edge[B].v = b, edge[B].w = c;
G[a].push_back(B ++);
}

inline void in() {
int i, j, a, b;
scanf("%d%d%d%d", &N, &K, &H, &R);
for(i = 1;i <= R;i ++) {
scanf("%d%d", &a, &b);
addEdge(b, a, 0);
if(a < b) for(j = a+1;j < b;j ++) {
addEdge(a, j, -1);
} else {
for(j = b+1;j < a;j ++) {
addEdge(a, j, -1);
}
}
}
for(i = 1;i <= N;i ++) {
addEdge(10009, i, 0);
addEdge(K, i, 0);
}
}

inline void solve() {
int i, x, sz;
memset(d, 0x3f, sizeof(d));
inq[10009] = 1;
d[10009] = 0;
Q.push(10009);
while(!Q.empty()) {
x = Q.front(); Q.pop(); inq[x] = 0;
sz = G[x].size();
for(i = 0;i < sz;i ++) {
Edge& e = edge[G[x][i]];
if(d[x] + e.w < d[e.v]) {
d[e.v] = d[x] + e.w;
if(!inq[e.v]) inq[e.v] = 1, Q.push(e.v);
}
}
}
for(i = 1;i <= N;i ++) {
printf("%d\n", d[i] + (H + d[K]));
}
}

int main() {
in();
solve();
return 0;
}
```

这道题最重要的结论是：
如果我们将i看到j视作i向j连一条有向线段，整张图构好一定不会出现线段相互交叉(端点不算相交且可以覆盖)，且每一个节点只能向外连接两条有向线段(这个好像没什么太大用......)。
然后就是递归操作，我是将左向右覆盖的线段做opt=0递归，反之做opt=1递归。
因为没什么人做这题所以我也没有可以什么借鉴的题解......代码比较挫先放这...如果有人有好一点的算法就不要理我算了QAQ

code:

type
ss=record
dt,nt:longint;
end;
var
hd1,hd2:array[1..2,0..10001]of longint;
p:array[0..10001]of longint;
edge:array[1..100000]of ss;
i,n,k,o,l,r,tot,maxh,x,y:longint;

procedure dfs(l,r,h,opt:longint);
var tmp,k,tmpk:longint;
begin
if(l=r)or(l+1=r)then exit;
if(opt=0)then
begin
k:=l;
while(k<=r)do
begin
tmpk:=0;
if(hd2[2][k]<>0)then
begin
tmp:=hd2[2][k];
while(tmp<>0)do
begin
if(edge[tmp].dt>tmpk)and((k<>l)and(edge[tmp].dt<=r)or(k=l)and(edge[tmp].dt<r))then
begin
opt:=1;
tmpk:=edge[tmp].dt;
end;
tmp:=edge[tmp].nt;
end;
end;
if(k<>l)and(k<>r)and(hd1[2][k]<>0)and(edge[hd1[2][k]].dt>tmpk)then
begin
opt:=0;
tmpk:=edge[hd1[2][k]].dt;
end;
if(tmpk<>0)then
begin
if(p[k]=0)then p[k]:=h;
if(p[tmpk]=0)then p[tmpk]:=h;
dfs(k,tmpk,h-1,opt) ;
k:=tmpk;
end else begin
if(p[k]=0)then p[k]:=h;
inc(k);
end;
end;
end else begin
k:=r;
while(k>=l)do
begin
tmpk:=n;
if(hd2[1][k]<>0)then
begin
tmp:=hd2[1][k];
while(tmp<>0)do
begin
if(edge[tmp].dt<tmpk)and((k<>r)and(edge[tmp].dt>=l)or(k=r)and(edge[tmp].dt>l))then
begin
opt:=0;
tmpk:=edge[tmp].dt;
end;
tmp:=edge[tmp].nt;
end;
end;
if(k<>l)and(k<>r)and(hd1[1][k]<>0)and(edge[hd1[1][k]].dt<tmpk)then
begin
opt:=1;
tmpk:=edge[hd1[1][k]].dt;
end;
if(tmpk<>n)then
begin
if(p[k]=0)then p[k]:=h;
if(p[tmpk]=0)then p[tmpk]:=h;
dfs(tmpk,k,h-1,opt) ;
k:=tmpk;
end else begin
if(p[k]=0)then p[k]:=h;
dec(k);
end;
end;
end;
end;
procedure add_edge2(x,y:longint);
var o:longint;
begin
inc(tot);
if(x>y)then o:=1 else o:=2;
edge[tot].dt:=y;
edge[tot].nt:=hd2[o][x];
hd2[o][x]:=tot;
end;
procedure add_edge1(x,y:longint);
var o:longint;
begin
inc(tot);
if(x>y)then o:=1 else o:=2;
edge[tot].dt:=y;
edge[tot].nt:=hd1[o][x];
hd1[o][x]:=tot;
end;
begin
assign(input,'1801.in'); assign(output,'1801.out');
reset(input); rewrite(output);
read(n,k,maxh,o);
for i:=1 to o do
begin
read(x,y);
add_edge1(x,y);
add_edge2(y,x);
end;
p[1]:=maxh;
p[k]:=maxh;
p[n]:=maxh;
dfs(0,n+1,maxh,0);
for i:=1 to n do writeln(p[i]);
close(output);
end.