题意：
有N个在一条直线上的房子, 每个房子有着不同的高度, 一个超人可以将这些房子左右移动但不能改变房子之间的相对位置.现在超人要从最矮的房子跳到刚好比他高的房子上面, 且每次跳的房子都要比当前房子要高.那么最后超人肯定会跳到最高的房子上面, 现在给出超人能够跳的最远距离, 问: 如何摆放这些房子, 使得超人能够经过所有的房子跳到最高的房子, 又要使最矮的房子和最高的房子之间的距离最远？(摘自讨论区)
思路：由于超人跳跃的序列是已定的，所以在想建图的时候会遇到当前点的后继点在它的后面、在它的前面两种情况，所以我们需要将它们统一一个方向(位置靠前的点指向位置靠后的点)，做的时候确实考虑到了。为什么这么做？后面便体现出来了。还有一个约束条件是：两点不在同一个坐标且元素顺序得保持初始顺序，即d[i]-d[i-1]>=1，所以再进行一次变换就是去建立i到i-1的且权值为-1的边。所以接下来可能进行的操作就是跑一遍最低点到最高点的SPFA。但是发现当最高点在最低点左边时，会发现SPFA就会沿着-1的边到达最高点，导致答案错误，所以确定方向此时就体现出来了。所以为保证答案的非负性和正确性，当最低点在最高点左边时，就跑从最低点到最高点SPFA，当最低点在最高点右边时，就跑从最高点到最低点SPFA。
代码：
#include <algorithm> #include <iostream> #include <string.h> #include <cstdio> #include <queue> using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 1005; const int maxm = 2005; struct node { int v, w, next; }edge[maxm]; int no, head[maxn]; int TT, N, D; pair<int, int> num[maxn]; int dis[maxn], vis[maxn], cnt[maxn]; queue<int> q; int cmp(const pair<int, int> &a, const pair<int, int> &b) { return a.second < b.second; } inline void init() { no = 0; memset(head, -1, sizeof head); } inline void add(int u, int v, int w) { edge[no].v = v; edge[no].w = w; edge[no].next = head[u]; head[u] = no++; } int SPFA(int S, int T) { memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis); memset(cnt, 0, sizeof cnt); while(!q.empty()) q.pop(); dis[S] = 0; q.push(S); vis[S] = 1; while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; ++cnt[u]; if(cnt[u] > N) return -1; //☆--判断一个点入队超过N次才可以判定存在负权回路--☆ for(int k = head[u]; k != -1; k = edge[k].next) { int v = edge[k].v; if(dis[v] > dis[u]+edge[k].w) { dis[v] = dis[u]+edge[k].w; if(!vis[v]) vis[v] = 1, q.push(v); } } } return dis[T]; } int main() { //freopen("in.txt", "r", stdin); scanf("%d", &TT); for(int _ = 1; _ <= TT; ++_) { init(); scanf("%d %d", &N, &D); for(int i = 1; i <= N; ++i) { int x; scanf("%d", &x); num[i] = make_pair(i, x); if(i > 1) add(i, i-1, -1); } sort(num+1, num+N+1, cmp); for(int i = 2; i <= N; ++i) { int u = num[i].first; int v = num[i-1].first; if(u < v) swap(u, v); add(v, u, D); } if(num[1].first < num[N].first) printf("Case %d: %d\n", _, SPFA(num[1].first, num[N].first)); else printf("Case %d: %d\n", _, SPFA(num[N].first, num[1].first)); } return 0; }
继续加油~
