P7480题解

· · 题解

这道题目看上去好像直接贪心就可以了，但是，其实在某些情况下，是可以走回头路的，所以就不能直接贪心求解了。

那么，怎么做呢？有一条显而易见的性质，就是不管是否走回头路，一定是一口气走到一个比这个点油价低的地方或走到终点，那么令终点有一个虚拟的加油站，油价为 0，这样就可以把终点和加油站一起进行处理了。

同时，也一定是恰好走到这个方向上离它最近的加油站，这个也非常容易证明。

根据这条性质，就能想到图论中的最短路——对于所有点，找左右两边各一个离它最近的点，其中这两个点的油价都低于该点的油价，往这两个点连边，长度为从这个点正好到达另一个点的耗费，如果没有，就不连。最多连 2n 条边，可以用单调栈做到 O(n) 。由于建成的图是有向无环图，所以只需用拓扑排序即可。

思路是这样的，然而有些细节需要注意：起始点所在的加油站必须要保证入度为 0，即遇到起始点就不让它进栈。在拓扑排序的时候，必须使所有入度为 0 的点全部进队列，而不仅仅为起始点，否则 0 分，原因就是一些无关的点也可能会往必要的点连边，使得这些必要的点入度永远不会减为 0，导致出错。

这样做总时间复杂度为 O(n\log n)，瓶颈在于排序（输入的坐标不保证有序）。

代码如下：

#include<ctime>
#include<queue>
#include<cstdio>
#include<cctype>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2e5+7;
ll read(){
    char c;
    ll x=0,f=1;
    while(!isdigit(c=getchar()))
        f-=2*(c=='-');
    while(isdigit(c)){
        x=x*10+f*(c-48);
        c=getchar();
    }
    return x;
}
struct pos{
    ll x,c;
    pos(ll a=0,ll b=0){
        x=a;
        c=b;
    }
    friend bool operator <(pos a,pos b){
        return a.x<b.x;
    }
};
struct edge{
    ll to,val,nxt;
    edge(ll a=0,ll b=0,ll c=0){
        to=a;
        val=b;
        nxt=c;
    }
};
pos p[N];
edge e[N];
ll top,st[N];
ll tot,head[N];
ll n,s,t,x,c,sx,tx,in[N],f[N];
void add(ll u,ll v,ll w){
    ++in[v];
    e[++tot]=edge(v,w,head[u]);
    head[u]=tot;
}
void topo(){
    queue<ll>q;
    for(ll i=1;i<=n;++i){
        if(!in[i])
            q.push(i);
    }
    for(ll i=1;i<=n;++i)
        f[i]=5e18;//最大值可能会达到2e18
    f[sx]=0;//只有起始点的f值为0，其他均为正无穷
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        for(ll i=head[u];i;i=e[i].nxt){
            ll v=e[i].to;
            ll w=e[i].val;
            if(f[v]>f[u]+w)
                f[v]=f[u]+w;
            if(!--in[v])
                q.push(v);
        }
    }
}
int main(){
    n=read();
    s=read();
    t=read();
    for(ll i=1;i<=n;++i){
        c=read();
        x=read();
        p[i]=pos(x,c);
    }
    ++n;
    p[n]=pos(t);
    sort(p+1,p+n+1);
    for(ll i=1;i<=n;++i){
        if(p[i].x==s)
            sx=i;
        if(p[i].x==t&&!p[i].c)
            tx=i;
    }
    for(ll i=1;i<=n;++i){
        while(top&&p[st[top]].c>=p[i].c){
            st[top]=0;
            --top;
        }
        if(top)
            add(i,st[top],(p[i].x-p[st[top]].x)*p[i].c);
        if(i^sx){//如果不为起始点，那么就使它进栈
            ++top;
            st[top]=i;
        }
    }
    while(top){
        st[top]=0;
        --top;
    }
    for(ll i=n;i;--i){
        while(top&&p[st[top]].c>=p[i].c){
            st[top]=0;
            --top;
        }
        if(top)
            add(i,st[top],(p[st[top]].x-p[i].x)*p[i].c);
        if(i^sx){
            ++top;
            st[top]=i;
        }
    }
    topo();
    printf("%lld",f[tx]);
    return 0;
}