传送门
题意
给出一个 \(n\) 个点 \(m\) 条边的无向图，边有边权，经过一条边 \((u,v,w)\) 的代价是 \(\min(走到u的路径上的最小边权,w)\)。（即前缀最小）
问从 \(1\) 走到 \(n\) 的最短路。
思路
肯定是要模仿 dijikstra 的过程来做。我们 dijikstra 时，是拿一条边 \((u,v,w)\) 松弛，来更新 \(dis_v\)，是考虑边的贡献。
显然，最后走出来路径的边权一定是若干连续段。
一个连续段的贡献取决于：
- 开头的边权
- 连续段长度
用到连续段长度，记 \(len_{u,v}\) 表示 \(u\) 到 \(v\) 的经过边个数最小，可以 floyd \(O(n ^ 3)\) 来计算。
我们在 dijikstra 时，对每条边 \((u,v,w)\) 去考虑它作为一个连续段的开头时的贡献。
要枚举连续段的结尾那个点 \(t\)，这样，整个连续段的权值就是 \((len_{v,t}+1) \times w\)。
接着，就可以用 \(dis_u + (len_{v, t} + 1) \times w\) 来更新 \(dis_t\)。
另一种思考方式（by DE_aemmprty）
不从边入手，从贡献序列入手
观察贡献序列（路径上边权序列），发现是连续段，一个从 \(u\) 到 \(v\) 的连续段要求路径上所有的边权 \(>= w_0\)，其中 \(w_0\) 是开头的边权。
发现如果一个从 \(u\) 到 \(v\) 的路径不满足这样的约束，即 \(\exists w_1 \in E_{u \rightarrow v} < w_0\)，那么从 \(w_1\) 处断开形成新的连续段一定优于这种方案。
也就是说，这种方案就算考虑了也不会有影响，而想排除掉很难，于是可以不管，然后执行前文的算法流程即可。这也是一个 trick：最优性问题中，当方案有不好处理的限制条件时，若不考虑该限制不会让方案变优，则可以忽视。
分析复杂度，插入到优先队列里的插入量是 \(O(nm)\) 的（因为每条边都会枚举 \(t\)，分别是 \(O(m)\)、\(O(n)\)），总复杂度就是 \(O(n^3+nm \log (nm))\)。显然起飞。
考虑优化，上述过程实现时，是每次从优先队列中取出 \(u\)，枚举 \(u\) 的一条出边 \((u, v, w)\)，然后每条边枚举 \(t\) 并直接入队。
在枚举这么多条边时，会大量出现同一个点入队的情况，这之间 \(dis\) 更大的显然更劣，没有必要入队。
于是先离线（离的是枚举边的线），最后对每个 \(t\) 取最优的入队，分析插入量：\(O(n^2)\)（每个点插入 \(O(n)\) 次），时间复杂度 \(O(n ^ 3 + nm + n^2 \log (n^2))\)。
代码
link
const int N = 505;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector<pair<ll, int>> e[N];
ll len[N][N];
ll dis[N];
void floyd(){rep(k, 1, n){rep(i, 1, n){rep(j, 1, n){chkmn(len[i][j], len[i][k] + len[k][j]);}}}
}
void dijikstra(){priority_queue<pair<ll, int>, vector< pair<ll, int> >, greater< pair<ll, int> >> q;memset(dis, 0x3f, sizeof(dis));dis[1] = 0;q.push({dis[1], 1});while(!q.empty()){auto [dis_u, u] = q.top(); q.pop();if(dis_u > dis[u]) continue;vector<ll> tmp(n + 1, inf);for(auto [v, w] : e[u]){rep(t, 1, n){chkmn(tmp[t], 1ll * (len[v][t] + 1) * w + dis_u);}}rep(i, 1, n){if(dis[i] > tmp[i]){q.push({dis[i] = tmp[i], i});}}}
}
void solve_test_case(){n = read(), m = read();memset(len, 0x3f, sizeof(len));rep(i, 1, n) len[i][i] = 0;rep(i, 1, m){int u = read(), v = read(), w = read();e[u].push_back({v, w});e[v].push_back({u, w});len[u][v] = 1;len[v][u] = 1;}floyd();dijikstra();write(dis[n]);
}