poj 1613 Cave Raider 用 SPFA 求最短路：TaoToken 统一 Key 跑通样例

1. POJ 1613 Cave Raider 到底在考什么带时间窗的最短路建模POJ 1613 Cave Raider 这道题第一次读题的人十有八九会被那一长串「关闭时间、打开时间」绕晕。它本质上是一道最短路题但和普通 Dijkstra 模板题不一样的地方在于边的可用性随时间变化。你可以把它理解成一条隧道像地铁闸机某些时间段闸机关闭你正好走到一半就会被夹住所以出发前必须算清楚「现在进去能不能在闸机关闭前走出来」。题目给的信息是n 个洞穴n ≤ 50m 条隧道m ≤ 500起点 s终点 t起始时间为 0。每条隧道有三个基础属性两个端点、通过耗时 w后面跟着一串递增的正整数交替表示「关闭时刻」和「打开时刻」。比如10 14 5 6 7 8 9意思是隧道连接 10 和 14走完要 5 个单位时间6 时刻关闭、7 时刻打开、8 时刻又关闭、9 时刻又打开9 之后永远打开。这里有个关键细节关闭到打开这段时间隧道在「清理」人在里面会死。所以你不能在关闭时刻正好卡在隧道里。换句话说如果你在时刻costu到达隧道入口想通过这条耗时 w 的隧道必须满足「进入后到走完的整个区间 [costu, costuw] 都落在某个开放区间内」。我试过直接套普通 SPFA结果样例第一个就 WA原因就是没处理这个时间窗。正确的松弛条件是dist[v] dist[u] edge(u,v)但这个edge(u,v)不是固定值而是「在 dist[u] 时刻从 u 出发最早能到达 v 的时刻」。这个值需要针对每条边的开放区间单独算。适合谁看正在刷 POJ / 准备算法竞赛、已经会写 SPFA 模板但卡在这道题时间窗处理上的同学。核心检索词就是「POJ 1613 SPFA 最短路 时间窗」下面我会把建图、时间窗计算、SPFA 队列模板、样例验证一步步拆开最后用 TaoToken 统一 Key 调模型帮你核对复杂度和定位 WA/TLE。先说清楚为什么用 SPFA 而不是 Dijkstra因为这里的「边权」依赖于到达时间不是静态的Dijkstra 的贪心前提被破坏而 SPFA 的队列松弛天然适合这种「到达时间变了就要重新松弛邻居」的场景。n 只有 50m 最多 500SPFA 完全够用不用担心被卡。2. TaoToken 统一 Key 前置把模型调试通道接进来写这道题的时候最容易卡住的不是 SPFA 本身而是两个地方一是时间窗的边界判断还是二是样例输出对不上时不知道错在哪。这时候用 TaoToken 统一 Key 调模型帮你逐行核对逻辑比自己在纸上推快得多。TaoToken 是一个统一的大模型 API 接入通道你拿一个 Key 就能调用多种模型用来做代码审查、复杂度核对、报错解释都很顺手。官网入口是 https://taotoken.net/?utm_sourcetaotoken_aicg_blog_endutm_mediumcsdnutm_campaignrewriteutm_content API 地址是 https://taotoken.net/api 这个不加 UTM。前置准备分三步第一步注册后在控制台创建 API Key。控制台地址 https://taotoken.net/console?utm_sourcetaotoken_aicg_blog_endutm_contentconsoleutm_campaignrewrite 进去后找到 API Keys 页面新建一个 Key复制保存。注意 Key 只在创建时完整显示一次丢了就得重建。第二步确认你要用的模型 ID。TaoToken 支持对话模型和编码模型做算法调试我一般用编码能力强的模型。模型列表可以在文档里查https://taotoken.net/doc?utm_sourcetaotoken_aicg_blog_endutm_contentdocutm_campaignrewrite 。第三步把 Base URL、Key、Model ID 三件套配好。如果你用 Cline、CC Switch 这类工具配置项就是这三个。下面给一个通用的 JSON 配置片段路径按你实际工具放{ provider: taotoken, baseUrl: https://taotoken.net/api, apiKey: sk-你的TaoToken密钥, model: 你的模型ID, temperature: 0.2 }如果你用的是 Claude Code 这类命令行工具配置思路一样把 Base URL 指向https://taotoken.net/apiKey 填进去Model ID 选编码模型即可。想直接在线对话验证模型是否通可以打开模型对话页https://taotoken.net/?utm_sourcetaotoken_aicg_blog_endutm_contentmodel-chatutm_campaignrewrite 。这里提醒一句TaoToken 是统一 API 通道不是让你绕过什么限制它只是把多个模型的调用收敛到一个 Key 上方便你在刷题时随时切模型做代码审查。配好之后你就可以把 POJ 1613 的代码贴进去让模型帮你检查时间窗边界。3. 可复制配置建图结构 时间窗函数 SPFA 模板这一节是全文核心我把 POJ 1613 的完整可复制实现拆成三块建图、时间窗计算、SPFA。你直接抄进 C 就能跑。先说建图。因为两个洞穴之间可能有多条隧道而且同一条隧道两个方向都能走所以用vectorNode v[maxn][maxn]存v[u][v]表示从 u 到 v 的所有隧道。每个 Node 存通过耗时 w、开放区间数组 a、区间数量 sz。#include iostream #include cstdio #include cstring #include queue #include vector #define maxn 55 using namespace std; const int INF 0x3f3f3f3f; int n, m, sx, ex; bool vis[maxn]; int dist[maxn]; char s[1000005]; struct Node { int w, sz; int a[40]; // a[0]0, 之后成对存 关闭/打开 时刻 } cur; vectorNode v[maxn][maxn]; queueint q;读入部分要特别小心因为每行隧道信息的整数个数不固定最多 35 个所以用gets读整行再手动解析。解析时把数字依次取出前三个是 u、v、w后面全是时间点。这里有个坑时间点个数可能是奇数表示最后一个关闭时刻之后永远关闭也可能是偶数表示最后一个打开时刻之后永远打开。代码里用(k-3)%2判断偶数就补一个 INF 表示「之后一直开着」奇数就保持原样表示「之后一直关着」。void read() { int i, k 0, t 0, uu, vv, w, flag 0, len; len strlen(s); s[len] x; s[len1] \0; for (i 0; s[i] ! \0; i) { if (s[i] 0 s[i] 9) { flag 1; t t * 10 s[i] - 0; } else { if (flag) { k; flag 0; if (k 1) uu t; else if (k 2) vv t; else if (k 3) { w t; cur.w w; } else cur.a[k-3] t; t 0; } } } cur.a[0] 0; if ((k - 3) % 2 0) { cur.a[k-2] INF; cur.sz k - 2; } else cur.sz k - 3; v[uu][vv].push_back(cur); v[vv][uu].push_back(cur); }时间窗计算函数getcost是整道题最容易写错的地方。它的输入是从 uu 到 vv 的第 k 条隧道、当前到达 uu 的时刻 costu。输出是「最早能到达 vv 的时刻」如果这条隧道在当前时刻无法通过返回 -1。逻辑是遍历所有开放区间[a[i], a[i1]]i 从 0 开始每次加 2如果costu a[i1]说明这个区间已经过去了continue如果costu落在[a[i], a[i1]]内且costu w a[i1]说明现在进去能在关闭前出来直接返回costu w否则costu 在区间之前或者当前区间放不下检查这个开放区间的长度a[i1] - a[i]是否 w如果够长就等到a[i]再进返回a[i] w。int getcost(int uu, int vv, int k, int costu) { int i, sz v[uu][vv][k].sz; for (i 0; i sz; i 2) { if (costu v[uu][vv][k].a[i1]) continue; else if (costu v[uu][vv][k].a[i1] costu v[uu][vv][k].a[i]) { if (costu v[uu][vv][k].w v[uu][vv][k].a[i1]) return costu v[uu][vv][k].w; } else { if ((v[uu][vv][k].a[i1] - v[uu][vv][k].a[i]) v[uu][vv][k].w) return v[uu][vv][k].a[i] v[uu][vv][k].w; } } return -1; }SPFA 主体从起点入队每次取出 nx遍历所有可能的邻居 i对v[nx][i]里的每条隧道算 getcost取最小值 mi如果dist[i] mi就松弛并入队。void SPFA() { int i, j, nx, sz, mi, cost; memset(vis, 0, sizeof(vis)); while (!q.empty()) q.pop(); dist[sx] 0; vis[sx] 1; q.push(sx); while (!q.empty()) { nx q.front(); q.pop(); vis[nx] 0; for (i 1; i n; i) { sz v[nx][i].size(); if (!sz) continue; mi INF; for (j 0; j sz; j) { cost getcost(nx, i, j, dist[nx]); if (cost ! -1 mi cost) mi cost; } if (dist[i] mi) { dist[i] mi; if (!vis[i]) { vis[i] 1; q.push(i); } } } } }主函数注意scanf(%d,n)读到 0 结束每读完第一行四个整数后要gets(s)吃掉换行再循环 m 次gets(s)读隧道。输出时dist[ex] INF打印数值否则打印*。int main() { int i; while (scanf(%d, n), n) { scanf(%d%d%d, m, sx, ex); // init: 清空 vis/dist/v memset(vis, 0, sizeof(vis)); memset(dist, 0x3f, sizeof(dist)); for (i 1; i n; i) for (int j 1; j n; j) v[i][j].clear(); gets(s); for (i 1; i m; i) { gets(s); read(); } SPFA(); if (dist[ex] INF) printf(%d\n, dist[ex]); else printf(*\n); } return 0; }这套代码的关键点就三个v[u][v]存多条边、getcost处理时间窗、SPFA 里对每条边取最小到达时间。把这三块拼起来样例就能过。4. 验证请求与成功结果样例输入输出逐行核对代码写完别急着提交先用题目给的样例跑一遍。样例输入比较长我把它整理成可复制的形式你直接存成in.txt2 2 1 2 1 2 5 4 10 14 20 24 30 1 2 6 2 10 22 30 6 9 1 6 1 2 6 5 10 1 3 7 8 20 30 40 2 4 8 5 13 21 30 3 5 10 16 25 34 45 2 5 9 22 32 40 50 3 4 15 2 8 24 34 4 6 10 32 45 56 65 5 6 3 2 5 10 15 2 3 5 2 9 19 25 2 2 1 2 1 2 7 6 9 12 1 2 9 8 12 19 0编译运行g -O2 -o cave cave.cpp ./cave in.txt期望输出16 55 *逐行解释一下这三个结果方便你确认自己代码逻辑对不对第一组2 2 1 2两条隧道都连接 1 和 2。第一条耗时 5开放区间是 [0,4]、[10,14]、[20,24]、[30,∞)。第二条耗时 6开放区间是 [0,2]、[10,22]、[30,∞)。从 1 出发时刻 0走第一条0 进 5 出但 4 就关了不行等的话第一条要等到 10 才能进15 出。走第二条0 进 6 出但 2 就关了不行。所以最优是等第一条到 10 进15 出但答案是 16。再算第二条在 [10,22] 开放10 进 16 出16 ≤ 22可行所以 16。这就是为什么答案是 16 而不是 15——第一条在 10 时刻的开放区间是 [10,14]长度 4 5放不下得等到 20。所以 16 是对的。第二组答案是 55第三组2 2 1 2两条隧道开放区间都很短凑不出可行路径输出*。如果你跑出来第一个是 15说明getcost里没检查区间长度是否够 w如果第二个对不上多半是时间窗边界写成了。这两个是最常见的 WA 点。想快速验证模型能不能帮你核对可以把这段代码和样例贴到模型对话页 https://taotoken.net/?utm_sourcetaotoken_aicg_blog_endutm_contentmodel-chatutm_campaignrewrite 让它逐行走一遍 getcost通常几秒就能指出边界问题。5. 本篇常见错排查401、local proxy failed、reading choices、OAuth刷这道题时报错分两类一类是算法本身的 WA/TLE一类是调 TaoToken 时的接入报错。分开说。算法侧最常见的三个坑第一个是getcost返回 -1 时没跳过导致mi被错误更新。注意代码里if (cost ! -1 mi cost)这个 -1 判断不能少否则不可达的边会被当成有效值。第二个是时间窗边界。题目说「关闭时刻到打开时刻之间在清理」所以进入时刻 costu 必须满足costu a[i]且costu w a[i1]。如果你写成costu w a[i1]就会漏掉「正好在关闭瞬间出来」的合法情况样例第一组会算成 15 或更大。第三个是读入。gets读整行但第一行四个整数后面还有换行必须先用一个gets(s)吃掉否则第一条隧道信息会被当成空行。另外每行整数个数不固定手动解析时k的计数要准cur.a[0]0这个补丁不能忘。接入侧报错对照401 UnauthorizedKey 错了或没带。检查请求头里Authorization: Bearer sk-xxxKey 从控制台 https://taotoken.net/api-keys?utm_sourcetaotoken_aicg_blog_endutm_contentapi-keysutm_campaignrewrite 重新复制一份。local proxy failed本地代理配置和 Base URL 冲突。把 Base URL 直接设成https://taotoken.net/api不要额外挂本地转发。reading choices类报错通常是响应体解析失败多半是 Model ID 填错或模型不支持当前请求格式。去文档 https://taotoken.net/doc?utm_sourcetaotoken_aicg_blog_endutm_contentdocutm_campaignrewrite 核对模型 ID。OAuth相关报错如果你用的是 Claude Code 这类工具OAuth 流程和 API Key 是两套。用 TaoToken 统一 Key 时走 API Key 模式别混用 OAuth 登录态。TLE 的话n50、m500SPFA 最坏情况也不会超POJ 给 1000MS 足够。如果你 TLE检查是不是在 SPFA 里对每条边重复做了太多字符串解析——解析应该在读入阶段完成SPFA 里只做数值计算。6. 语义一致 CTA把统一 Key 用在长期刷题与调试上这道题跑通之后你会发现真正花时间的不是 SPFA 模板而是时间窗这种「题目特有的建模细节」。这类细节靠人眼盯很容易漏用模型做代码审查就省事很多。如果你只是偶尔调一次模型核对代码用模型对话页就够了https://taotoken.net/?utm_sourcetaotoken_aicg_blog_endutm_contentmodel-chatutm_campaignrewrite 。把代码和样例贴进去让它逐行解释 getcost 的边界。如果你在长期刷题、准备竞赛或者要写 Agent 自动跑测试用例建议用 Coding Plan一个 Key 覆盖多种编码模型切换不用重新配https://taotoken.net/coding-plan?utm_sourcetaotoken_aicg_blog_endutm_contentcoding-planutm_campaignrewrite 。接入文档和 API Key 管理分别在这里文档 https://taotoken.net/doc?utm_sourcetaotoken_aicg_blog_endutm_contentdocutm_campaignrewrite API Keys https://taotoken.net/api-keys?utm_sourcetaotoken_aicg_blog_endutm_contentapi-keysutm_campaignrewrite 。把 Base URL 固定成https://taotoken.net/apiKey 和 Model ID 配好下次遇到 POJ 1613 这种时间窗最短路直接让模型帮你核对 getcost 的区间判断比反复提交试错快得多。