题意

有一个包含 NN 个关卡的游戏。起初，只有第 11 个关卡可以游玩。

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

  • 花费 AiA_i 的时间通关，并解锁关卡 i+1i+1。
  • 花费 BiB_i 的时间通关，并解锁关卡 XiX_i。

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

思路

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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];
}