（F魔法传送门）Dijkstra算法(图的最短路径)迪杰斯特拉算法)
Dijkstra算法(图的最短路径)初始 起点adista0其余∞第1轮 选b(2)更新c3、d5集合{a,b}第2轮 选c(3)更新e7、f4集合{a,b,c}第3轮 选f(4)无更新集合{a,b,c,f}第4轮 选d(5)更新e6集合{a,b,c,f,d}第5轮 选e(6)无更新全节点完结 最终最短距离 b2c3d5e6f4时间复杂度堆优化版:O(mlogn) --用优先队列快速取出距离最小的节点适合稀疏图暴力版:O(n*n) --适合节点少的稠密图适用范围求解单源最短路径(一个起点到其余的节点)硬性要求:所有边权0(存在负边权用SPFA)核心思想dist[i]:起点到节点i的已知最短距离初始化除了起点外全部设为无穷大用小根堆每次取出当前距离最小的未确定的节点对该节点所有邻边做松弛:若dist[v]dist[u]w 就更新dist[v]并堆入堆vis[i]标记节点最短路径已确定避免后续重复n:节点总数m:边总数数组作用g[]邻接表存图稀疏图首选比邻接矩阵省空间dist[]动态维护起点到每个节点的最短距离vis[]标记节点是否拿到最终最短路避免重复计算分层 Dijkstra最多 k 次免费 / 减半边权路径回溯新增pre[]数组存前驱节点反向还原路线多起点最短路初始把所有起点同时入堆即可[P4779 【模板】单源最短路径标准版 - 洛谷][(https://www.luogu.com.cn/problem/P4779)#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define PLL pairll, ll #define YES coutYESendl; #define NO coutNOendl; using namespace std; const ll INF1e15; const ll MAXN100005; vectorPLLg[MAXN]; //邻接表:g[u]{v,边权w} ll dist[MAXN];//最短距离 bool vis[MAXN]; void dijkstra(ll start,ll n) { for(ll i1;in;i) { dist[i]INF; } // memset(vis,0,sizeof(vis)); dist[start]0; priority_queuePLL,vectorPLL,greaterPLLq; q.push({0,start}); //{距离节点编号}初始状态传入 while(!q.empty()) { PLL curq.top(); ll dcur.fi; ll ucur.se; q.pop(); if(ddist[u]) { continue; } for(auto edge:g[u]) { ll vedge.fi; ll wedge.se; if(dist[v]dw) { dist[v]dw; q.push({dist[v],v}); } } } } int main() { IOS ll n,m,s; cinnms; for(ll i1;iMAXN;i) { g[i].clear(); } for(ll i1;im;i) { ll u,v,w; cinuvw; g[u].emplace_back(v,w);//有向图 // g[v].emplace_back(u,w); //无向图 } dijkstra(s,n); for(ll i1;in;i) { if(i!n) { coutdist[i] ; } else { coutdist[i]; } } coutendl; // coutfixedsetprecision(x) ; return 0; }F-魔法传送门_河南萌新联赛2026第三场郑州轻工业大学核心:将用多少次魔法加入状态中两种转移遍历 u 的每条边 u‑v边权 w假设现在状态在 u已用 j 次魔法当前距离 d转移 1不使用魔法留在同一层老老实实付边权 w 走到 v魔法次数不变。dis[v][j] d w 如果满足更新把 (dw , v , j) 丢进优先队列。转移 2使用本次魔法跳到下一层仅当 jk这条边直接免费不需要加 w魔法次数 1(j1)。dis[v][j1] d 如果满足更新把 (d , v , j1) 丢进优先队列。只有 jk 才能做这个转移不能超过允许的 k 次#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define PLL pairll, ll #define YES coutYESendl; #define NO coutNOendl; using namespace std; typedef pairll,pairll,llP; const ll INF1e18; const ll MAXN100005; using namespace std; ll n,m,k; vectorPLLg[1005]; ll dis[1005][15];//距离魔法 int main() { IOS cinnmk; for(ll i1;im;i) { ll u,v,w; cinuvw; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } for(ll i1;in;i) { for(ll j0;jk;j) { dis[i][j]INF; } } dis[1][0]0; priority_queueP,vectorP,greaterPq; q.push({0,{1,0}}); while(!q.empty()) { auto nowq.top(); q.pop(); ll dnow.fi; ll unow.se.fi; ll usednow.se.se; if(ddis[u][used]) { continue; } for(auto edge :g[u]) { ll vedge.fi; ll wedge.se; if(dis[v][used]dw) { dis[v][used]dw; q.push({dis[v][used],{v,used}}); } if(usedkdis[v][used1]d) { dis[v][used1]d; q.push({dis[v][used1],{v,used1}}); } } } ll ansINF; for(ll j0;jk;j) { ansmin(ans,dis[n][j]); } coutansendl; // coutfixedsetprecision(x) ; return 0; }
Dijkstra算法(图的最短路径)初始 起点adista0其余∞第1轮 选b(2)更新c3、d5集合{a,b}第2轮 选c(3)更新e7、f4集合{a,b,c}第3轮 选f(4)无更新集合{a,b,c,f}第4轮 选d(5)更新e6集合{a,b,c,f,d}第5轮 选e(6)无更新全节点完结 最终最短距离 b2c3d5e6f4时间复杂度堆优化版:O(mlogn) --用优先队列快速取出距离最小的节点适合稀疏图暴力版:O(n*n) --适合节点少的稠密图适用范围求解单源最短路径(一个起点到其余的节点)硬性要求:所有边权0(存在负边权用SPFA)核心思想dist[i]:起点到节点i的已知最短距离初始化除了起点外全部设为无穷大用小根堆每次取出当前距离最小的未确定的节点对该节点所有邻边做松弛:若dist[v]dist[u]w 就更新dist[v]并堆入堆vis[i]标记节点最短路径已确定避免后续重复n:节点总数m:边总数数组作用g[]邻接表存图稀疏图首选比邻接矩阵省空间dist[]动态维护起点到每个节点的最短距离vis[]标记节点是否拿到最终最短路避免重复计算分层 Dijkstra最多 k 次免费 / 减半边权路径回溯新增pre[]数组存前驱节点反向还原路线多起点最短路初始把所有起点同时入堆即可[P4779 【模板】单源最短路径标准版 - 洛谷][(https://www.luogu.com.cn/problem/P4779)#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define PLL pairll, ll #define YES coutYESendl; #define NO coutNOendl; using namespace std; const ll INF1e15; const ll MAXN100005; vectorPLLg[MAXN]; //邻接表:g[u]{v,边权w} ll dist[MAXN];//最短距离 bool vis[MAXN]; void dijkstra(ll start,ll n) { for(ll i1;in;i) { dist[i]INF; } // memset(vis,0,sizeof(vis)); dist[start]0; priority_queuePLL,vectorPLL,greaterPLLq; q.push({0,start}); //{距离节点编号}初始状态传入 while(!q.empty()) { PLL curq.top(); ll dcur.fi; ll ucur.se; q.pop(); if(ddist[u]) { continue; } for(auto edge:g[u]) { ll vedge.fi; ll wedge.se; if(dist[v]dw) { dist[v]dw; q.push({dist[v],v}); } } } } int main() { IOS ll n,m,s; cinnms; for(ll i1;iMAXN;i) { g[i].clear(); } for(ll i1;im;i) { ll u,v,w; cinuvw; g[u].emplace_back(v,w);//有向图 // g[v].emplace_back(u,w); //无向图 } dijkstra(s,n); for(ll i1;in;i) { if(i!n) { coutdist[i] ; } else { coutdist[i]; } } coutendl; // coutfixedsetprecision(x) ; return 0; }F-魔法传送门_河南萌新联赛2026第三场郑州轻工业大学核心:将用多少次魔法加入状态中两种转移遍历 u 的每条边 u‑v边权 w假设现在状态在 u已用 j 次魔法当前距离 d转移 1不使用魔法留在同一层老老实实付边权 w 走到 v魔法次数不变。dis[v][j] d w 如果满足更新把 (dw , v , j) 丢进优先队列。转移 2使用本次魔法跳到下一层仅当 jk这条边直接免费不需要加 w魔法次数 1(j1)。dis[v][j1] d 如果满足更新把 (d , v , j1) 丢进优先队列。只有 jk 才能做这个转移不能超过允许的 k 次#includebits/stdc.h #define ll long long #define endl \n #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define ull unsigned long long #define fi first #define se second #define PLL pairll, ll #define YES coutYESendl; #define NO coutNOendl; using namespace std; typedef pairll,pairll,llP; const ll INF1e18; const ll MAXN100005; using namespace std; ll n,m,k; vectorPLLg[1005]; ll dis[1005][15];//距离魔法 int main() { IOS cinnmk; for(ll i1;im;i) { ll u,v,w; cinuvw; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } for(ll i1;in;i) { for(ll j0;jk;j) { dis[i][j]INF; } } dis[1][0]0; priority_queueP,vectorP,greaterPq; q.push({0,{1,0}}); while(!q.empty()) { auto nowq.top(); q.pop(); ll dnow.fi; ll unow.se.fi; ll usednow.se.se; if(ddis[u][used]) { continue; } for(auto edge :g[u]) { ll vedge.fi; ll wedge.se; if(dis[v][used]dw) { dis[v][used]dw; q.push({dis[v][used],{v,used}}); } if(usedkdis[v][used1]d) { dis[v][used1]d; q.push({dis[v][used1],{v,used1}}); } } } ll ansINF; for(ll j0;jk;j) { ansmin(ans,dis[n][j]); } coutansendl; // coutfixedsetprecision(x) ; return 0; }
![Claude Code 结构化用量限额行（Structured Usage Rate-Limit Rows）：limits[] 字段的服务器权威语义与客户端渲染契约](http://pic.xiahunao.cn/yaotu/Claude Code 结构化用量限额行（Structured Usage Rate-Limit Rows）：limits[] 字段的服务器权威语义与客户端渲染契约)
