题解 P7480 【【C】Reboot from Blue】

看到这一题，首先有一个非常 naive 的做法是在每两个点之间连单向边，代表从一个点到另一个点，然后跑最短路。但是边数会达到 $O(n^2)$，无法通过。 考虑减少边的数量，注意到当我们从点 $i$ 走到点 $j$ 时，如果其中出现了花费比 $i$ 点更低的点 $k$，那么我们大可以先跑到 $k$ 再跑到 $j$，由此想到单调队列优化。 以 $s$ 为界，在左边右边分别建立单调队列，只有这上面的点才能成为中转站。建图时显然同一个单调队列内相同的点连边，$s$ 向左右单调队列队头连边。接下来考虑左右单调队列之间怎样连边，我们发现从 $s$ 的一边 $i$开到另一边 $j$ 时，中间所有大于 $i$ 花费的值全部可以跳过，所以我们可以在单调队列上二分，找到可以开到最远的加油站，并连边。 这样边数降到 $O(n)$，可以通过。 ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<queue> #include<map> using namespace std; #define int long long struct node { int c,x; bool operator <(const node &other) const { return x^other.x? x<other.x:c<other.c; } }a[100001]; struct edge { int nxt,to,weight; }e[100001<<2]; int n,s,t,p,dis[100001],cnt,tot,h[100001]; bool vis[100001]; vector<pair<int,int> > q1,q2; map<pair<int,int>,int> mp; inline void add(int x,int y,int w) { e[++tot].nxt=h[x]; h[x]=tot; e[tot].to=y; e[tot].weight=w; } inline void dijkstra() { priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; q.push(make_pair(0,mp[make_pair(a[p].c,a[p].x)])); while(!q.empty()) { pair<int,int> k=q.top(); q.pop(); if(vis[k.second]) continue; vis[k.second]=1; dis[k.second]=k.first; for(register int i=h[k.second];i;i=e[i].nxt) if(!vis[e[i].to]) q.push(make_pair(k.first+e[i].weight,e[i].to)); } } signed main() { scanf("%lld%lld%lld",&n,&s,&t); for(register int i=1;i<=n;++i) scanf("%lld%lld",&a[i].c,&a[i].x); a[++n].x=t+1; a[n].c=1ll<<30; sort(a+1,a+n+1); for(register int i=1;i<=n;++i) { if(a[i].x<s) continue; if(a[i].x==s) p=i; if(a[i].x>t) break; if(q2.empty()||q2.back().first>a[i].c) { mp[make_pair(a[i].c,a[i].x)]=++cnt; if(!q2.empty()) add(mp[q2.back()],mp[make_pair(a[i].c,a[i].x)],q2.back().first*(a[i].x-q2.back().second)); q2.push_back(make_pair(a[i].c,a[i].x)); } } for(register int i=p-1;i>=1;--i) if(q1.empty()||min(q1.back().first,a[p].c)>a[i].c) { mp[make_pair(a[i].c,a[i].x)]=++cnt; if(!q1.empty()) add(mp[q1.back()],mp[make_pair(a[i].c,a[i].x)],q1.back().first*(q1.back().second-a[i].x)); q1.push_back(make_pair(a[i].c,a[i].x)); } mp[make_pair(0,t)]=++cnt; add(mp[q2.back()],mp[make_pair(0,t)],q2.back().first*(t-q2.back().second)); q2.push_back(make_pair(0,t)); reverse(q2.begin(),q2.end()); reverse(q1.begin(),q1.end()); for(register int i=0;i<(int)q1.size();++i) { int it=lower_bound(q2.begin(),q2.end(),make_pair(q1[i].first,1ll<<30))-q2.begin()-1; if(it>=0&&it<(int)(q2.size())) add(mp[q1[i]],mp[q2[it]],q1[i].first*(q2[it].second-q1[i].second)); } for(register int i=0;i<(int)q2.size();++i) { int it=lower_bound(q1.begin(),q1.end(),make_pair(q2[i].first,1ll<<30))-q1.begin()-1; if(it>=0&&it<(int)(q1.size())) add(mp[q2[i]],mp[q1[it]],q2[i].first*(q2[i].second-q1[it].second)); } dijkstra(); printf("%lld\n",dis[mp[make_pair(0,t)]]); return 0; } ```