用html表格做的网站,互联网公司做什么的,泰安网络公司平台,注册网站借钱平台犯不犯法Help Jimmy POJ - 1661 题意#xff1a;大致是一个人从某个点开始下落#xff0c;下落的速度是1m/s#xff0c;然后在平台上的时候可以左右移动#xff0c;移动的速度也是1m/s#xff0c;但是这里有一个限制#xff0c;就是说每次下落的距离不能超过一个给定的数值。问你… Help Jimmy POJ - 1661 题意大致是一个人从某个点开始下落下落的速度是1m/s然后在平台上的时候可以左右移动移动的速度也是1m/s但是这里有一个限制就是说每次下落的距离不能超过一个给定的数值。问你从起始点下落到地板最少需要多少s。
题解这道题我看到的时候第一感觉是最短路建图方法就是对于每一个平台的两个端点编号为2*i1和2*i2考虑这个从端点所能下落到的下一个平台的两个端点比如根据上一个平台的某个端点到下一个最近的平台的两个端点所需要的时间来建立边边权就是耗费的时间
最后别忘了从起点开始的建边以及端点到地板的建边
动态规划的做法等会了再补上 #include iostream
#include cstdio
#include vector
#include algorithm
#include queue
#include cstring
using namespace std;
#define int long long
const int MAXN 2005;
const int INF 1e18;
int N,X,Y,MAX;
//int G[MAXN][MAXN];
//vectorint G[MAXN];
int head[MAXN];
struct edge{int v;int next;int cost;
}Es[MAXN1];
int d[MAXN];
int cnt;
typedef pairint,int P;
struct node{int x1,x2,h;friend bool operator(node n1,node n2){return n1.h n2.h;}
};
node ns[MAXN];
void dijkstra(int x){for(int i 0;i MAXN;i)d[i] INF;d[x] 0;priority_queueP,vectorP,greaterP que;que.push(P(0,x));while(!que.empty()){P p que.top();que.pop();int dis p.first;int v p.second;if(d[v] dis) continue;//for(int i 0;i 2*N2;i){for(int e head[v];e! -1;e Es[e].next){int cost Es[e].cost;int i Es[e].v;if(cost d[v] d[i]){d[i] d[v] cost;que.push(P(d[i],i));}}}
}
inline void add_edge(int i,int j,int cost){//G[i][j] cost;Es[cnt].v j;Es[cnt].cost cost;Es[cnt].next head[i];head[i] cnt;
}
void init(){cnt 0;memset(head,-1,sizeof(head));
}
main(){int t;scanf(%lld,t);while(t--){init();scanf(%lld%lld%lld%lld,N,X,Y,MAX);for(int i 0;i N;i){int x1,x2,h;scanf(%lld%lld%lld,x1,x2,h);ns[i].x1 x1;ns[i].x2 x2;ns[i].h h;}sort(ns,nsN);//create graphfor(int i 0;i N;i){int l 0,r 0;int f 1;for(int j i 1;j N;j){if(ns[i].h - ns[j].h MAX){f 0;break;}if(!l ns[i].x1 ns[j].x1 ns[i].x1 ns[j].x2){l 1;add_edge(2*i1,2*j1,ns[i].h - ns[j].h ns[i].x1 - ns[j].x1);add_edge(2*i1,2*j2 ,ns[i].h - ns[j].h ns[j].x2 - ns[i].x1);}if(!r ns[i].x2 ns[j].x1 ns[i].x2 ns[j].x2){r 1;add_edge(2*i2,2*j1,ns[i].h - ns[j].h ns[i].x2 - ns[j].x1);add_edge(2*i2,2*j2,ns[i].h - ns[j].h ns[j].x2 - ns[i].x2);}if(r l) break;}if(!f)continue; if(!l ns[i].h MAX){add_edge(2*i1,2*N1,ns[i].h);}if(!r ns[i].h MAX){add_edge(2*i2,2*N1,ns[i].h);}}int f 0;for(int i 0;i N;i){if(X ns[i].x1 X ns[i].x2 Y ns[i].h Y - ns[i].h MAX){add_edge(0,2*i1,Y - ns[i].h X - ns[i].x1);add_edge(0,2*i2,Y - ns[i].h ns[i].x2 - X);f 1;break;}}if(!f){if(Y MAX){add_edge(0,2*N1,Y);}}dijkstra(0);coutd[2*N1]endl;}
}
