子任务一：DFS 暴力枚举（$n\le10$）

思路详解

1.状态定义

• 用布尔数组 vis[1...n] 标记哪些草场已访问。

• 递归函数 dfs(u, cnt, acc)：

  • u：当前所在草场编号；
  • cnt：已访问（包含当前）的草场个数；
  • acc：到目前为止的魔力消耗总和。

2.终止条件

• 如果 cnt == n，说明已串联过所有草场，此时只需再回到草场 1，更新答案：

  ans = min(ans, acc + cost[u][1]);
  

3.递推过程

• 否则，枚举所有未访问的草场 v (2..n)：

  if (!vis[v]) {
    vis[v] = true;
    dfs(v, cnt+1, acc + cost[u][v]);
    vis[v] = false;
  }
  

• 这样可以保证每条路径恰好访问一次，且遍历所有可能。

代码示例（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int n;
ll cost[16][16], ans = INF;
bool vis[16];

// u: 当前草场编号
// cnt: 已访问草场个数
// acc: 累计魔力消耗
void dfs(int u, int cnt, ll acc) {
    if (cnt == n) {
        // 回到 1 号草场，完成一次环
        ans = min(ans, acc + cost[u][1]);
        return;
    }
    for (int v = 2; v <= n; v++) {
        if (!vis[v]) {
            vis[v] = true;
            dfs(v, cnt + 1, acc + cost[u][v]);
            vis[v] = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> cost[i][j];

    vis[1] = true;
    dfs(1, 1, 0);
    cout << ans << "\n";
    return 0;
}

时间复杂度： 每层递归最多分支数 $n-1$（第一层尝试 $n-1$ 条边），深度 $n-1$，时间复杂度约 $O\bigl((n-1)!\bigr)\,\simeq\,O(n!)。$

子任务二：全排列枚举（$n\le12$）

思路详解

1.排列对象

• 草场 $2\dots n$ 的顺序直接决定访问顺序，先编号放 vector<int> p = {2,3,…,n}。

2.枚举方法

• 调用全排列函数，逐个产生字典序下一个排列。

3.计算路径消耗

• 路径：1 → p[0] → p[1] → … → p.back() → 1，
• 累加每一步的 cost[a][b]。

4.维护最小值

ll sum = cost[1][p[0]];
for (int i = 0; i + 1 < p.size(); i++)
    sum += cost[p[i]][p[i+1]];
sum += cost[p.back()][1];
ans = min(ans, sum);

代码示例（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
ll cost[16][16];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    if(n == 1){
    	cout<<0<<"\n";
    	return 0;
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> cost[i][j];

    vector<int> p;
    for(int i = 2; i <= n; i++) p.push_back(i);

    ll ans = LLONG_MAX;
    do {
        ll sum = cost[1][p[0]];
        for(int i = 0; i + 1 < (int)p.size(); i++)
            sum += cost[p[i]][p[i+1]];
        sum += cost[p.back()][1];
        ans = min(ans, sum);
    } while(next_permutation(p.begin(), p.end()));

    cout << ans << "\n";
    return 0;
}

时间复杂度： 排列数 $(n-1)!$，每次路径累加 $n$ 步，总计 $O\bigl(n\cdot (n-1)!\bigr).$

子任务三：DFS+ 剪枝 / 状态压缩 DP（$n\le15$）

方法 A：DFS + 剪枝

由于数据保证随机生成，所以我们可以通过剪枝来优化操作次数。

1.全局最小边权

ll minEdge = INF;
for (i!=j) minEdge = min(minEdge, cost[i][j]);

用于估计 “最优下界”。

2.剪枝条件

如果当前已用 acc，还剩 $(n - cnt + 1)$ 步（包括回到 $1$）的最小可能消耗是 ：

那么，若：

则无须继续枚举，可直接返回。

4.伪代码概览

dfs(u, cnt, acc):
  if acc + (n-cnt+1)*minEdge >= ans: return
  if cnt == n:
    ans = min(ans, acc + cost[u][1])
    return
  for 每个未访问 v:
    标记 vis[v]=true
    dfs(v, cnt+1, acc + cost[u][v])
    还原 vis[v]=false

5.代码示例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int n;
ll cost[16][16], ans=INF, minEdge=INF;
bool vis[16];

void dfs(int u, int cnt, ll acc){
    // 剪枝
    if(acc + (n - cnt + 1) * minEdge >= ans) return;
    if(cnt == n){
        ans = min(ans, acc + cost[u][1]);
        return;
    }
    for(int v = 2; v <= n; v++){
        if(!vis[v]){
            vis[v]=true;
            dfs(v, cnt+1, acc + cost[u][v]);
            vis[v]=false;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    if(n == 1){
    	cout<<0<<"\n";
    	return 0;
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++){
        cin>>cost[i][j];
        if(i!=j) minEdge=min(minEdge,cost[i][j]);
      }
    vis[1]=true;
    dfs(1,1,0);
    cout<<ans<<"\n";
    return 0;
}

复杂度 理论最坏仍 $O(n!)$，但在随机矩阵上剪枝极其有效，能应付 $n\le15$。

方法 B：状态压缩 DP

1.状态定义

• 用位掩码 S 表示已访问的草场集合，保证第 1 号在集合中。
• dp[S][i] = 从 1 出发，访问完 S 且最后停在 i 的最小消耗。

2.转移方程 对每个 S，对每个 i∈S 且 i≠1，伪代码为：

for j not in S:
  dp[S∪{j}][j] = min(dp[S∪{j}][j],
                     dp[S][i] + cost[i][j]);

3.初始化

dp[1<<0][0] = 0;  // 集合 {1}，最后停在 1 的代价 0

4.答案计算 完全集合 full = (1<<n)-1，最优答案为

ans = min_{i=1..n-1}( dp[full][i] + cost[i][0] );

5.代码示例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    if(n == 1){
    	cout<<0<<"\n";
    	return 0;
    }
    vector<vector<ll>> cost(n, vector<ll>(n));
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        cin>>cost[i][j];

    int N = 1<<n;
    static ll dp[1<<15][15];
    // 初始化为无穷大
    for(int s=0;s<N;s++)
      for(int i=0;i<n;i++)
        dp[s][i] = INF;
    dp[1<<0][0] = 0;

    // 按子集枚举
    for(int s=0;s<N;s++){
      if(!(s&1)) continue;  // 必须包含草场 1
      for(int i=0;i<n;i++){
        if(!(s&(1<<i))) continue;
        ll cur = dp[s][i];
        if(cur==INF) continue;
        for(int j=0;j<n;j++){
          if(s&(1<<j)) continue;
          int t = s|(1<<j);
          dp[t][j] = min(dp[t][j], cur + cost[i][j]);
        }
      }
    }

    ll ans = INF;
    int full = (1<<n)-1;
    for(int i=1;i<n;i++)
      ans = min(ans, dp[full][i] + cost[i][0]);

    cout << ans << "\n";
    return 0;
}

时间复杂度

• 枚举子集 $2^n$，
• 内层枚举尾点 $i$（$n$）和下一个点 $j$（$n$）， 总计 $O(n^2\cdot2^n)$. 空间复杂度$O(n\cdot2^n)$，对 $n\le15$ 足够。

解题思路

1. 数据结构

   • vector<bool> gate(N+1)：门的开关状态，gate[i]=true 表示门 $i$ 开启。
   • struct Sheep { int p; long long e; };
   • vector<Sheep> sheep(1+S)：下标 $1\ldots$ 动态增至 $S+Q$，不存在的小羊不会被删，只在操作时判断是否合法。
   • long long T = 0; 全局时间。
   • vector<tuple<long long,int,long long>> logs; 存储 STATUS 输出。

2. 指令调度 遍历每条指令，先将 T += 1（指令基础耗时），再根据指令种类：

   • OPEN/CLOSE i：切换 gate[i]。
   • SPAWN id：若 1≤id<sheep.size()，将 sheep.push_back(sheep[id])。
   • MOVE id L/R：若 id 合法且对应门开启，则让 p 向左或向右环形移动，且 e -= 1。
   • JUMP id k L/R：同 MOVE，但循环尝试最多 $k$ 步，遇门关闭立即停。每成功一步 e--。
   • WAIT id t：T += t；若 id 合法，sheep[id].e += t。
   • ENERGY id x：若 id 合法，sheep[id].e += x。
   • SYNC a b：若 a,b 都合法，令两只小羊 p = min(p[a],p[b])。
   • SWAP a b：若合法，交换两只小羊的 p。
   • TELEPORT id p：若 id 合法且 $1\le p\le N$，令 sheep[id].p = p。
   • STATUS id：若 id 合法，记录 (T, sheep[id].p, sheep[id].e)；否则 (T, -1, 0)。

3. 边界与忽略规则

   • 所有指令无论参数是否越界，都先 T++。
   • 只有当引用的小羊 id 在 1…sheep.size()-1 且门号/圈号合法时，才执行对应操作；否则仅消耗时间，不改变状态（但 STATUS 仍要输出 “-1,0”）。

4. 输出 执行完所有指令后，先打印 logs.size()，再逐行输出每个 (T,P,E)。

代码示例（C++）

#include <bits/stdc++.h>
using namespace std;

struct Sheep { int p; long long e; };

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q, S;
    cin >> N >> Q >> S;

    vector<bool> gate(N+1);
    for(int i = 1; i <= N; i++){
        int x; cin >> x;
        gate[i] = (x == 1);
    }

    vector<Sheep> sheep(1+S);
    for(int i = 1; i <= S; i++){
        cin >> sheep[i].p;
        sheep[i].e = 0;
    }

    long long T = 0;
    vector<tuple<long long,int,long long>> logs;
    logs.reserve(Q);

    string cmd;
    while(Q--){
        cin >> cmd;
        T++;  // 每条指令基础耗时 1

        if(cmd == "OPEN"){
            int i; cin >> i;
            if(1 <= i && i <= N) gate[i] = true;
        }
        else if(cmd == "CLOSE"){
            int i; cin >> i;
            if(1 <= i && i <= N) gate[i] = false;
        }
        else if(cmd == "SPAWN"){
            int id; cin >> id;
            if(id >= 1 && id < (int)sheep.size())
                sheep.push_back(sheep[id]);
        }
        else if(cmd == "MOVE"){
            int id; char d;
            cin >> id >> d;
            if(id >= 1 && id < (int)sheep.size()){
                int cur = sheep[id].p;
                int nxt = (d == 'L' ? (cur==1?N:cur-1)
                                   : (cur==N?1:cur+1));
                int door = (d == 'L' ? (cur==1?N:cur-1) : cur);
                if(gate[door]){
                    sheep[id].p = nxt;
                    sheep[id].e--;
                }
            }
        }
        else if(cmd == "JUMP"){
            int id, k; char d;
            cin >> id >> k >> d;
            if(id >= 1 && id < (int)sheep.size()){
                while(k--){
                    int cur = sheep[id].p;
                    int nxt = (d == 'L' ? (cur==1?N:cur-1)
                                       : (cur==N?1:cur+1));
                    int door = (d == 'L' ? (cur==1?N:cur-1) : cur);
                    if(!gate[door]) break;
                    sheep[id].p = nxt;
                    sheep[id].e--;
                }
            }
        }
        else if(cmd == "WAIT"){
            int id; long long t;
            cin >> id >> t;
            T += t; 
            if(id >= 1 && id < (int)sheep.size())
                sheep[id].e += t;
        }
        else if(cmd == "ENERGY"){
            int id; long long x;
            cin >> id >> x;
            if(id >= 1 && id < (int)sheep.size())
                sheep[id].e += x;
        }
        else if(cmd == "SYNC"){
            int a, b; cin >> a >> b;
            if(a>=1&&a<(int)sheep.size()&&b>=1&&b<(int)sheep.size()){
                int mn = min(sheep[a].p, sheep[b].p);
                sheep[a].p = sheep[b].p = mn;
            }
        }
        else if(cmd == "SWAP"){
            int a, b; cin >> a >> b;
            if(a>=1&&a<(int)sheep.size()&&b>=1&&b<(int)sheep.size()){
                swap(sheep[a].p, sheep[b].p);
            }
        }
        else if(cmd == "TELEPORT"){
            int id, p; cin >> id >> p;
            if(id>=1&&id<(int)sheep.size() && 1<=p&&p<=N)
                sheep[id].p = p;
        }
        else if(cmd == "STATUS"){
            int id; cin >> id;
            if(id>=1&&id<(int)sheep.size())
                logs.emplace_back(T, sheep[id].p, sheep[id].e);
            else
                logs.emplace_back(T, -1, 0);
        }
    }

    // 输出所有 STATUS 记录
    cout << logs.size() << "\n";
    for(auto &tup : logs){
        long long t; int p; long long e;
        tie(t,p,e) = tup;
        cout << t << " " << p << " " << e << "\n";
    }
    return 0;
}

时间复杂度： $O(Q \times K)$，其中 $K=\max(\text{JUMP 步数})\le20$，故整体 $O(Q)$.

空间复杂度： $O(N + S + Q)$，用于存门状态、小羊数组与日志存储。

子任务一/二：暴力枚举（$n\le 10^3,\,q\le 10^3$）

思路详解

• 使用递归或二重循环直接计算 $\binom{n}{k}$（例如杨辉三角），
• 对每个查询，枚举 $k=l_i\ldots r_i$ 并累加。

代码示例（C++）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

int C[1005][1005];

int main(){
    int n,q; 
    cin>>n>>q;
    // 预处理杨辉三角
    for(int i=0;i<=n;i++){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
    }
    while(q--){
        int l,r; cin>>l>>r;
        long long ans=0;
        for(int k=l;k<=r;k++){
            ans=(ans + C[n][k])%MOD;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

时间复杂度：

• 预处理 $O(n^2)$。
• 每查询枚举区间 $\le n$，共 $O(q\cdot n)$。 总体 $O(n^2 + qn)$，能轻松通过子任务一/二。

子任务二/三：阶乘+反阶乘（$n\le10^3,\,q\le10^3$）

思路详解

1. 预先计算 $0\ldots n$ 的阶乘 fac[i] 与逆元阶乘 ifac[i]：

   $$ \binom{n}{k} = \mathrm{fac}[n]\times \mathrm{ifac}[k]\times \mathrm{ifac}[n-k]\bmod M. $$

2. 每个查询直接枚举区间求和，$O(r_i-l_i+1)\le O(n)$。

代码示例（C++）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

long long modpow(long long a, long long e=MOD-2){
    long long r=1;
    while(e){
        if(e&1) r=r*a%MOD;
        a=a*a%MOD; e>>=1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,q; cin>>n>>q;
    vector<long long> fac(n+1,1), ifac(n+1,1);
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
    ifac[n]=modpow(fac[n]);
    for(int i=n;i>0;i--) ifac[i-1]=ifac[i]*i%MOD;

    while(q--){
        int l,r; cin>>l>>r;
        long long ans=0;
        for(int k=l;k<=r;k++){
            ans = (ans + fac[n]*ifac[k]%MOD*ifac[n-k])%MOD;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

时间复杂度：

• 阶乘与逆元预处理 $O(n + \log\,MOD)$。
• 每查询 $O(r-l+1)\le O(n)$，总体 $O(n + qn)$，可通过子任务二/三。

应该没有人 $O(n + qn)$ 过了子任务四吧。——SudoXue

子任务四/五：前缀和 + 组合递推（$n\le10^6,\,q\le10^5$）

思路详解

1. 预处理 inv 数组

   $$ \mathrm{inv}[1]=1,\quad \mathrm{inv}[i]= (M - M/i)\times \mathrm{inv}[M\%i]\bmod M. $$

2. 递推计算所有 $\binom{n}{k}$

   C0 = 1;                // C(n,0)
   for k = 1..n:
     Ck = C_{k-1} * (n - k + 1) % M * inv[k] % M;
   

3. 前缀和数组 S

   $$S[0]=C_0,\quad S[k]=S[k-1]+C_k\ (\bmod\,M).$$

4. 查询答案

   $$ \sum_{k=l}^{r} \binom{n}{k} = (S[r] - (l>0?S[l-1]:0) + M)\bmod M. $$

代码示例（C++）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,q; 
    cin>>n>>q;
    vector<long long> inv(n+1,1), C(n+1), S(n+1);
    for(int i=2;i<=n;i++){
        inv[i] = (MOD - MOD/i) * inv[MOD%i] % MOD;
    }

    C[0]=1;
    for(int k=1;k<=n;k++){
        C[k] = C[k-1] * (n - k + 1) % MOD * inv[k] % MOD;
    }
    S[0]=C[0];
    for(int k=1;k<=n;k++){
        S[k] = (S[k-1] + C[k]) % MOD;
    }

    while(q--){
        int l,r; cin>>l>>r;
        long long ans = S[r] - (l>0?S[l-1]:0);
        if(ans<0) ans += MOD;
        cout<<ans<<"\n";
    }
    return 0;
}

时间复杂度：

• 预处理 inv 与组合递推 $O(n)$。
• 构造前缀和 $O(n)$。
• 每查询 $O(1)$。 总体 $O(n + q)$，可轻松应对 $n\le10^6, q\le10^5$。

子任务一/二：暴力找路（$N,M\le 10^3$）

思路详解

1. 对每条路径 $(u,v)$：

   • 用 DFS/BFS 在树上寻找一条从 $u$ 到 $v$ 的简单路径，同时记录父节点。
   • 从 $v$ 反向沿父指针回到 $u$，得到整条路径节点列表。
   • 对路径上每个节点 $x$ 做 cnt[x]++。

2. 最后：遍历 $1\ldots N$，统计 cnt[i] ≥ K 的节点个数。

代码示例（C++）

#include <bits/stdc++.h>
using namespace std;
int N,M,K;
vector<vector<int>> g;
vector<int> cnt, parent_;

vector<int> find_path(int u,int v){
    queue<int> q; 
    parent_.assign(N+1, -1);
    parent_[u]=0;
    q.push(u);
    while(!q.empty()){
        int x=q.front(); q.pop();
        if(x==v) break;
        for(int y:g[x]){
            if(parent_[y]==-1){
                parent_[y]=x;
                q.push(y);
            }
        }
    }
    vector<int> path;
    for(int cur=v; cur!=0; cur=parent_[cur])
        path.push_back(cur);
    return path;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N>>M>>K;
    g.assign(N+1,{});
    for(int i=1,u,v;i<N;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cnt.assign(N+1,0);

    while(M--){
        int u,v; cin>>u>>v;
        auto path = find_path(u,v);
        for(int x:path) 
            cnt[x]++;
    }

    int ans=0;
    for(int i=1;i<=N;i++)
        if(cnt[i]>=K) ans++;
    cout<<ans<<"\n";
    return 0;
}

子任务三：差分 + LCA（$N,M\le10^6$）

思路详解

1. 树的预处理

   • 建邻接表，做一次 DFS 从根 $1$ 出发，记录 depth[x]、parent[x]，并用倍增数组 up[x][j] 支持 $O(\log N)$ 的 LCA 查询。

2. 差分标记

   • 对每条路径 $(u,v)$：

     diff[u] += 1;
     diff[v] += 1;
     w = lca(u, v);
     diff[w] -= 1;
     if (parent[w] ≠ 0) diff[parent[w]] -= 1;
     

   • 这样做，相当于为整条 $u\to v$ 路径“打标记”。

3. 后序累加

   • 再次 DFS，自下而上：

     $$res[x] \;=\;diff[x]\;+\sum_{y\in\text{子节点}(x)}res[y] $$

   • 最终 $res[x]$ 就是节点 $x$ 被经过的总次数。

4. 统计结果

   • 遍历所有 $x$，计数满足 $res[x]\ge K$ 的节点数。

代码示例（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LOG = 20;            // 2^20 > 1e6
static int N, M, K;
static vector<int> g[1000005];
static int parent_[1000005], depth[1000005], up[1000005][LOG];
static ll diffCnt[1000005], resCnt[1000005];
ll answer = 0;

// 1) 建倍增与 depth
void dfs0(int u,int p){
    parent_[u]=p;
    up[u][0]=p;
    for(int j=1;j<LOG;j++)
        up[u][j] = up[ up[u][j-1] ][j-1];
    for(int v:g[u]){
        if(v==p) continue;
        depth[v]=depth[u]+1;
        dfs0(v,u);
    }
}

// 2) LCA 查询
int lca(int u,int v){
    if(depth[u]<depth[v]) swap(u,v);
    int diff=depth[u]-depth[v];
    for(int j=0;j<LOG;j++)
        if(diff>>j&1) u=up[u][j];
    if(u==v) return u;
    for(int j=LOG-1;j>=0;j--){
        if(up[u][j]!=up[v][j]){
            u=up[u][j];
            v=up[v][j];
        }
    }
    return parent_[u];
}

// 3) 后序累加
ll dfs1(int u,int p){
    ll sum = diffCnt[u];
    for(int v:g[u]){
        if(v==p) continue;
        sum += dfs1(v,u);
    }
    resCnt[u] = sum;
    if(sum >= K) answer++;
    return sum;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>N>>M>>K;
    for(int i=1,u,v;i<N;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs0(1,0);  // 预处理 parent_、depth、up

    // 差分标记每条路径
    for(int i=0,u,v;i<M;i++){
        cin>>u>>v;
        diffCnt[u]++; 
        diffCnt[v]++;
        int w = lca(u,v);
        diffCnt[w]--;
        if(parent_[w]) diffCnt[parent_[w]]--;
    }

    dfs1(1,0);  // 后序累加并统计
    cout<<answer<<"\n";
    return 0;
}

时间复杂度

• 建树 + 倍增预处理：$O(N\log N)$
• $M$ 条路径做差分：$O(M\log N)$（含 LCA）
• 后序累加：$O(N)$

总体：$O((N+M)\log N + N)$。

总思路：三维层图最短路

状态 $(u,a,b)$：到达节点 $u$ 时，已用幽蓝晶石 $a$（$0 \le a \le A$）、已用琥珀晶石 $b$（$0 \le b \le B$）的最短距离。

经边 $(u\to v,w)$ 有三种转移

在 $(A+1)(B+1)$ 层图上用 Dijkstra 即可。 答案为

子任务一：暴力枚举（$A,B\le 1;N\le300$）

思路详解

1. 枚举水晶布置

   • $A,B\le1$ ⇒ 最多改两条边。

   • 双重循环枚举：

     • free ∈ {-1 … M-1} 表示幽蓝安在哪条边（-1 代表不安）。
     • half ∈ {-1 … M-1} 表示琥珀安在哪条边且不同于 free。

2. 改权并跑普通最短路

   • 把选中的边权改写为 $0$ 或 $\lfloor w/2\rfloor$，其余保持原权。
   • 跑一次 Dijkstra/Floyd，取最小值。

代码核心

long long run(int free,int half,const vector<tuple<int,int,int>>& E,int N,int M){
    vector<vector<pair<int,int>>> g(N+1);
    for(int i=0;i<M;i++){
        auto [u,v,w]=E[i];
        if(i==free) w=0;
        else if(i==half) w/=2;
        g[u].push_back({v,w});
    }
    /* 普通 Dijkstra，返回 1→N 最短路，INF 表示不可达 */
}

时间复杂度 $(M+1)^2$ 次最短路，最坏约 $600^2 \times 600\log 300 \approx 3.6\times10^6$，轻松通过。

子任务二：$B=0$（只有幽蓝晶石）

思路详解

1. 一维层图 状态降为 $(u,a)$。

2. 转移

   • 原价：$(u,a)\to(v,a)$，花费 $w$；
   • 免费：$(u,a)\to(v,a+1)$，花费 $0;(a\le A)$。

3. Dijkstra 层数 $A+1\le31$，复杂度

   $$O\!\bigl((A+1)(N+M)\log N\bigr).$$

代码示例

/* idx(u,a) = u*(A+1)+a */
vector<ll> dist(1LL*(N+1)*(A+1), INF);
auto id=[&](int u,int a){return 1LL*u*(A+1)+a;};

dist[id(1,0)]=0; priority_queue<St> pq;
pq.push({0,1,0});               // St: d,u,a
while(!pq.empty()){
    auto [d,u,a]=pq.top(); pq.pop();
    if(d!=dist[id(u,a)]) continue;
    for(auto [v,w]:g[u]){
        if(d+w<dist[id(v,a)]){
            dist[id(v,a)]=d+w; pq.push({d+w,v,a});
        }
        if(a<A && d<dist[id(v,a+1)]){
            dist[id(v,a+1)]=d; pq.push({d,v,a+1});
        }
    }
}

空间　$(A+1)N$ 个 ll，≈ 25 MB。

子任务三：$A=0$（只有琥珀晶石）

• 与子任务二对称，状态 $(u,b)$。
• 把“免费转移”改为“折半转移（+$\lfloor w/2\rfloor$）”。
• 复杂度同 $O((B+1)(N+M)\log N)$。

子任务四/五：三维 Dijkstra（无额外限制）

思路详解

• 状态 $(u,a,b)$，层数 $(A+1)(B+1)\le31^2$。
• 使用下标压平：id = u*K + a*(B+1)+b, K=(A+1)(B+1)。
• priority_queue 维护最小距离。
• 全局最优剪枝：一旦到过终点，记录 best；若后续弹出的距离 ≥best，可直接丢弃。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge{int v; ll w;};
struct St{ll d; int u,a,b; bool operator<(St const& o)const{return d>o.d;}};

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N,M,A,B; cin>>N>>M>>A>>B;
    vector<vector<Edge>> g(N+1);
    for(int i=0,u,v;i<M;i++){ ll w; cin>>u>>v>>w; g[u].push_back({v,w}); }

    const int K=(A+1)*(B+1); const ll INF=4e18;
    auto id=[&](int u,int a,int b){return 1LL*u*K + 1LL*a*(B+1)+b;};
    vector<ll> dist(1LL*(N+1)*K, INF);

    priority_queue<St> pq;
    dist[id(1,0,0)]=0; pq.push({0,1,0,0});
    ll best=INF;

    while(!pq.empty()){
        auto cur=pq.top(); pq.pop();
        if(cur.d!=dist[id(cur.u,cur.a,cur.b)] || cur.d>=best) continue;
        if(cur.u==N){ best=cur.d; continue; }
        for(auto e:g[cur.u]){
            int v=e.v; ll w=e.w;
            /* 原价 */
            if(cur.d+w<dist[id(v,cur.a,cur.b)]){
                dist[id(v,cur.a,cur.b)]=cur.d+w;
                pq.push({cur.d+w,v,cur.a,cur.b});
            }
            /* 幽蓝 */
            if(cur.a<A && cur.d<dist[id(v,cur.a+1,cur.b)]){
                dist[id(v,cur.a+1,cur.b)]=cur.d;
                pq.push({cur.d,v,cur.a+1,cur.b});
            }
            /* 琥珀 */
            if(cur.b<B && cur.d+w/2<dist[id(v,cur.a,cur.b+1)]){
                dist[id(v,cur.a,cur.b+1)]=cur.d+w/2;
                pq.push({cur.d+w/2,v,cur.a,cur.b+1});
            }
        }
    }
    cout<<(best==INF? -1 : best)<<"\n";
    return 0;
}

复杂度

• 状态数：$(A+1)(B+1)N7$。
• 堆松弛：$O((A+1)(B+1)M\log((A+1)(B+1)N))$。