- 空间跳跃 8级2 2024.6
- 2025-03-05 22:09:49 @
#include<bits/stdc++.h>
#define inline inline __attribute__ ((always_inline))
using namespace std;
const int MAXN=1005;
int n,s,t,dis[2*MAXN];
vector<vector<pair<int,int>>>ed(2*MAXN);
deque<int>q;
class BOARD{
public:
int high,l,r;
int id;
}boa[MAXN];
inline bool cmp(BOARD x,BOARD y){
if(x.high!=y.high)return x.high>y.high;
return x.l<y.l;
}
inline void add_line(int fro,int to,int di){ed[fro].push_back(make_pair(to,di));}
inline int L(int id){return 2*id;}
inline int R(int id){return 2*id+1;}
inline void init(){
for(int i=1;i<=n;i++)
cin>>boa[i].l>>boa[i].r>>boa[i].high,boa[i].id=i;
sort(boa+1,boa+1+n,cmp);
bool f=1;
for(int i=1;i<=n;i++){
if(boa[i].id==s&&f)s=i,f=0;
if(boa[i].id==t){t=i;break;}
}
for(int i=s;i<t;i++){
add_line(L(i),R(i),boa[i].r-boa[i].l);
add_line(R(i),L(i),boa[i].r-boa[i].l);
for(int j=i+1;j<=t;j++)
if(boa[i].high>boa[j].high&&boa[i].l>boa[j].l&&boa[i].l<boa[j].r){
add_line(L(i),L(j),boa[i].high-boa[j].high+boa[i].l-boa[j].l);
break;
}
for(int j=i+1;j<=t;j++)
if(boa[i].high>boa[j].high&&boa[i].r>boa[j].l&&boa[i].r<boa[j].r){
add_line(R(i),R(j),boa[i].high-boa[j].high+boa[j].r-boa[i].r);
break;
}
}
}
inline void SPFA(){
dis[L(s)]=0;
int num=1,sum=0;
q.push_front(L(s));
while(!q.empty()){
while(dis[q.front()]*num<sum){
q.push_back(q.front());
q.pop_front();
}
int cur=q.front();
q.pop_front();
sum-=dis[cur];num--;
for(pair<int,int>i:ed[cur])
if(dis[i.first]>dis[cur]+i.second){
dis[i.first]=dis[cur]+i.second;
sum+=dis[i.first];
num++;
if(dis[i.first]>dis[q.front()])q.push_back(i.first);
else q.push_front(i.first);
}
}
}
signed main(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
memset(dis,0x3f,sizeof(dis));
cin>>n>>s>>t;
init();
SPFA();
if(dis[L(t)]==0x3f3f3f3f&&dis[R(t)]==0x3f3f3f3f)cout<<-1;
else cout<<min(dis[L(t)],dis[R(t)]);
return 0;
}
1 条评论
-
2230134娄耀 (2212238) LV 8 @ 2025-03-06 19:01:46
SPFA算法会有些特殊数据过不去,换成Dijkstra等算法可以解决
- 1
信息
- ID
- 2790
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 19
- 已通过
- 5
- 通过率
- 26%
- 上传者