差分约束瞎搞一下，话说这个数据不知道怎么回事，我的图按道理而言最多只有4n条边，开5n还不够？？必须6n？？
约束条件首先根据f函数可建立两点之间的约束，不妨设d[i]为i到0的距离，则对于f[i] == f[j] + 1(i>j)的情况，必定d[i] - d[j] >= 1,对于f[i] == f[j]的情况，必定d[j] - d[i] >= 0(i>j)
区间范围就不说了吧。
#include<cstdio> #include<cstdlib> #include<iostream> #include<string> #include<set> #include<algorithm> #include<vector> #include<queue> #include<list> #include<cmath> #include<cstring> #include<map> #include<stack> using namespace std; #define check(x,y) (x>=5&&y>=5&&x<n+5&&y<m+5) #define dight(chr) (chr>='0'&&chr<='9') #define alpha(chr) (chr>='a'&&chr<='z') #define rep(i,a,n) for(int i=a;i<n;++i) #define repe(i,a,n) for(int i=a;i<=n;++i) #define per(i,n,a) for(int i=n;i>=a;--i) #define loop(a) for(int i=0;i<a;++i) #define loope(a) for(int i=1;i<=a;++i) #define clc(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f3f3f3f #define maxn 100005 #define ull unsigned long long #define ll long long #define hashmod 99999839 #define mod 1000000000 #define repe(x,y,i) for(i=(x);i<=(y);++i) #define repne(x,y,i) for(i=(x);i<(y);++i) #define MAX(x,y) (x) < (y) ? (y) : (x); struct edge{ int to; int cost; int next; }G[600005]; int f,l,r,p[maxn],len; int head[maxn],n; ll dis[maxn]; bool inq[maxn]; void Read(int &n){char chr=getchar(),sign=1;for(;!dight(chr);chr=getchar())if(chr=='-')sign=-1; for(n=0;dight(chr);chr=getchar())n=n*10+chr-'0';n*=sign;} void Read(ll &n){char chr=getchar(),sign=1;for(;!dight(chr);chr=getchar())if (chr=='-')sign=-1; for(n=0;dight(chr);chr=getchar())n=n*10+chr-'0';n*=sign;} void spfa(int st){ queue<int> q; memset(inq,false,sizeof(inq)); for(int i = 0;i <= n;++i) dis[i] = INF; q.push(st); inq[st] = true; dis[st] = 0; while(!q.empty()){ int v = q.front(); q.pop(); inq[v] = false; for(int i = head[v];i;i = G[i].next){ edge& t = G[i]; if(dis[t.to] > dis[v] + t.cost){ dis[t.to] = dis[v] + t.cost; if(!inq[t.to]) q.push(t.to); } } } for(int i = 1;i < n;++i) printf("%lld ",dis[i]); printf("%lld ",dis[n]); } int main(){ //// freopen("a.in","r",stdin); // freopen("b.out","w",stdout); int T; scanf("%d",&T); while(T--){ scanf("%d",&n); len = 1; memset(head,0,sizeof(head)); memset(p,0,sizeof(p)); Read(f); p[f] = 1; for(int i = 2;i <= n;++i){ Read(f); if(f == 1){ G[len].to = i,G[len].cost = 0,G[len].next = head[p[1]],head[p[1]] = len,++len; p[f] = i; continue; } int t = p[f - 1]; G[len].to = t,G[len].cost = -1,G[len].next = head[i],head[i] = len,++len; t = p[f]; if(t) G[len].to = i,G[len].cost = 0,G[len].next = head[t],head[t] = len,++len; p[f] = i; } for(int i = 1;i <= n;++i){ Read(l),Read(r); G[len].to = 0,G[len].cost = -l,G[len].next = head[i],head[i] = len,++len; G[len].to = i,G[len].cost = r,G[len].next = head[0],head[0] = len,++len; } spfa(0); } return 0; }