AtCoder Beginner Contest 340 D - Super Takahashi Bros. 题解

题意

有一个包含 $N$ 个关卡的游戏。起初，只有第 $1$ 个关卡可以游玩。

在每个可以被游玩的关卡 $i$ 中，你可以进行以下两种操作：

• 花费 $A_i$ 的时间通关，并解锁关卡 $i+1$。
• 花费 $B_i$ 的时间通关，并解锁关卡 $X_i$。

输出解锁关卡 $N$ 所需的最短时间。

思路

看到这种题首先想到的当然是 dp，但对于这道题来说 dp 的转移顺序并不好确定，于是交了一发记忆化搜索却 WA 了。

这种情况下我们可以考虑建图，把关卡编号看成点，解锁关卡花费的时间看成边，然后我们就只需要对每个点 $i$ 到点 $i+1$ 连一条长度为 $A_i$ 的边，到点 $X_i$ 连一条长度为 $B_i$ 的边，直接以点 $1$ 为起点跑最短路即可，最终到点 $N$ 的距离就是答案。

代码

const int N = 2e5+5;

struct edge{
    int p1;
    int p2;
    ll val;
}edges[N*4];
int place[N];
ll d[N];

int ed = 0,n;
inline void add_edge(edge a){
    ed++;edges[ed] = a;
}

bool cmp(edge a,edge b){return a.p1<b.p1;}

void sort_edges(){
    sort(edges+1,edges+1+ed,cmp);
    int ned = 1;
    for(int i=1;i<=n;i++){
        bool flag = 0;
        while(edges[ned].p1==i){
            if(!flag){
                flag = 1;
                place[i] = ned;
            }
            ned++;
        }
    }
}

void dijkstra(){
    reset(d,0x3f);
    d[1] = 0;
    priority_queue<pair<ll,int>> pq;
    pq.push(mp_(0,1));
    while(!pq.empty()){
        int now = pq.top().snd;pq.pop();
        // cout<<now<<"\n";
        int ned = place[now];
        while(edges[ned].p1==now){
            if(d[now]+edges[ned].val<d[edges[ned].p2]){
                d[edges[ned].p2] = d[now]+edges[ned].val;
                pq.push(mp_(-d[edges[ned].p2],edges[ned].p2));
            }
            ned++;
        }
    }
}

void solve(){
    read(n);
    for(int i=1;i<n;i++){
        ll a,b;int x;
        read(a);add_edge((edge){i,i+1,a});
        read(b);read(x);
        add_edge((edge){i,x,b});
    }
    sort_edges();	//我的建图方法可能比较抽象，只要能看出来是建图跑最短路就行
    dijkstra();
    cout<<d[n];
}