悬关求调,样例不过
查看原帖
悬关求调,样例不过
917683
rnf5114楼主2023/11/19 20:57
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
int n,l[20010],r[20010],m,dist[40050],s[40050];
struct node{
	int zhong,w;
};
vector <node> v[40050];
void spfa(){
	dist[0]=0;
	for(int i=0;i<=2*n+1;i++){
		int Max=pow(2,31)-1,t=-1;
		for(int j=0;j<=2*n+1;j++){
			if(s[j]==0&&dist[j]<Max){
				Max=dist[j];
				t=j;
			}
		}
		if(t==-1)
			break;
		else{
			for(int j=0;j<v[t].size();j++){
				dist[v[t][j].zhong]=min(dist[v[t][j].zhong],dist[t]+v[t][j].w);
			}
		}
		s[t]=1;
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
	}
	for(int i=1;i<=n;i++){
		if(i==1){
			v[m].push_back({1,r[i]-1+r[i]-l[i]});
			v[m].push_back({2,r[i]-1});
			m++;
		}
		else if(i==n){
			v[m].push_back({2*n+1,n-l[i]});
			v[m+1].push_back({2*n+1,n-r[i]});
		}
		else{
			v[m].push_back({m+1,abs(l[i-1]-l[i])+r[i]-l[i]});
			v[m].push_back({m,abs(l[i-1]-r[i])+r[i]-l[i]});
			v[m+1].push_back({m,abs(r[i-1]-r[i])+r[i]-l[i]});
			v[m+1].push_back({m+1,abs(l[i]-r[i-1])+r[i]-l[i]});
			m+=2;
		}
	}
	for(int i=0;i<=2*n+1;i++){
		dist[i]=pow(2,31)-1;
	}
	spfa();
	cout<<dist[2*n+1]+n-1;
    return 0;
}


/*
       ┏┓   ┏┓
     ┏┛┻━━━┛┻┓
     ┃       ┃
     ┃   ━   ┃
     ┃ ┳┛ ┗┳ ┃
     ┃       ┃
     ┃   ┻   ┃
     ┃       ┃
     ┗━┓   ┏━┛Codes are far away from bugs with the animal protecting
         ┃   ┃    神兽保佑,代码无bug
         ┃   ┃
         ┃   ┗━━━┓
         ┃      ┣┓
         ┃     ┏┛
         ┗┓┓┏━┳┓┏┛
           ┃┫┫ ┃┫┫
           ┗┻┛ ┗┻┛     ○| ̄|_

*/

2023/11/19 20:57
加载中...