[CF

题目

题目背景
给生者的忠告：

不要踏进 狗熊岭 半步。在这里的人只有两种：被熊踩死的，和被狗咬死的。

如果你已经进来了，那么不要直视狗的眼睛。它的眼睛有一种魔力，可以将你的视线牢牢吸引住；在它的眼睛里，我看到自己倒映在里面，愚蠢、荒唐而渺小；在它的眼睛里，我看到人类是多么脆弱，看到人类不可颠覆的大自然的统治。

或者至少，不要引起熊的注意。那是渴望孤独的种族。靠近这份孤独的人，尸骨无存。哪怕 “弱者报团取暖”，也只会在刺骨的寒风中消散。

请记住，生命比理想更重要。挑战狗或熊的权威的人，只能在天堂找到同志者。

题意概要
传送门 to CF：给出有向带边权图。对于一条路径，设其经过的边的边权构成可重集 S S S，则 S S S 的前 min ⁡ ( k , ∣ S ∣ ) \min(k,|S|) min(k,∣S∣) 大的元素之和为该路径的权值。

求 s ⇝ t s\leadsto t s⇝t 最小权值路径。

数据范围与约定
点数 n ⩽ 1 0 3 n\leqslant 10^3 n⩽103，边数 m ⩽ 2000 m\leqslant 2000 m⩽2000，而 k ⩽ 1 0 3 k\leqslant 10^3 k⩽103 。边权为 1 0 9 10^9 109 以内的自然数。

思路

枚举第 k k k 大元素。跑最短路时要记录边权 w ⩾ v w\geqslant v w⩾v 的边数，只能 Bellman-Fort \text{Bellman-Fort} Bellman-Fort 做到单次 O ( n m ) \mathcal O(nm) O(nm)，总复杂度 O ( n m 2 ) \mathcal O(nm^2) O(nm2)，而且常数不小。

我们必须猜测可以仅通过一次普通最短路算法得到答案。动机是什么？理由是什么？

……

这里不是别处，正是 狗熊岭，狗和熊领导着天下。我害怕它们，不只因为狗锋利的牙齿，和熊坚守的孤独；最使我感到害怕的，最让我意识到人类不可能战胜自然的，是——

“野兽般敏锐的直觉。”

以前也曾相信，“在成为超越历代的火影之前，我是不会死的！” 可是后来，他分明承认了，他一直都知道自己就是阿修罗。他当然不会死。我会。

在这片森林里，我丢掉了学习的欲望，连同理想与希望，一齐被熊打散了。我慢慢懂了熊写下的话：“敢死不叫勇气，活着才需要勇气。” 因为活着，就要被吊打。

……

如果我们猜到了，可以用一次普通最短路，那么只需要构造函数 w ( x ) w(x) w(x) 使得
f ( S ) = c + ∑ x ∈ S w ( x ) f(S)=c+\sum_{x\in S}w(x) f(S)=c+x∈S∑w(x)

不小于 S S S 作为路径上所有边的边权的可重集时路径的权值，且存在 x x x 使其取等。

最自然的想法是，单峰且恰好在 x x x 为第 k k k 大时最小。只需要比 v v v 大的数提供 − 1 -1 −1 的导数，比 v v v 小的提供导数 0 0 0，然后加上全局 k k k 导数就能使得导数 = 0 =0 =0 的点为第 k k k 大值。

这样的函数，如果连续，则形如 w ( x ) = max ⁡ ( x − v , 0 ) w(x)=\max(x{\rm-}v,0) w(x)=max(x−v,0) 。不难验证 c = k v c=kv c=kv 。此时，最小值刚好能取到路径的原本权值！

总述：枚举第 k k k 大值 v v v，令边权 x x x 变为 max ⁡ ( x − v , 0 ) \max(x{\rm-}v,0) max(x−v,0) 后求一次最短路，将这个值 + k v +kv +kv 更新答案。

时间复杂度 O ( n m log ⁡ m ) \mathcal O(nm\log m) O(nmlogm) 。

代码

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG long for LONELINESS)
#include <cctype> // ZXY yydSISTER!!!
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){int a = 0, c = getchar(), f = 1;for(; !isdigit(c); c=getchar())if(c == '-') f = -f;for(; isdigit(c); c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}
inline void getMin(int &x, const int &y){if(y < x) x = y;
}
inline void getMin(llong &x, const llong &y){if(y < x) x = y;
}typedef std::pair<int,int> PII;
const int MAXN = 3003, MAXM = 3003;
PII* g[MAXN]; int deg[MAXN], n, k;
const llong INF = (1ll<<60)-1;
# define cmp(x,y) (dis[x] < dis[y] ? x : y)
# define upd(x) for(int j=x+n; j>>=1; ) pq[j] = cmp(pq[j<<1],pq[j<<1|1])
llong dis[MAXN]; int pq[MAXN<<1];
llong check(const int &w, const int &s, const int &t){fill(dis,dis+n+1,INF); dis[s] = 0;memset(pq+1,0,n<<2); rep(i,1,n) pq[i+n] = i;for(int x=pq[1]=s; pq[1]; ){x = pq[1], pq[x+n] = 0; upd(x);PII* const _end = g[x]+deg[x];for(PII* i=g[x]; i!=_end; ++i){const int cost = std::max(0,i->second-w);if(dis[i->first] > dis[x]+cost){dis[i->first] = dis[x]+cost;upd(i->first); // reload}}}return dis[t]+llong(w)*k;
}
llong normal(const int &s, const int &t){llong *now = dis; static llong nxt[MAXN];fill(now+1,now+n+1,INF), now[s] = 0;rep0(_,0,k){ // exactly k edgesmemcpy(nxt+1,now+1,n<<3); // may stayrep(i,1,n){ // one stepPII* const _end = g[i]+deg[i];for(PII* j=g[i]; j!=_end; ++j)getMin(nxt[j->first],now[i]+j->second);}memcpy(now+1,nxt+1,n<<3);}return now[t];
}int a[MAXM], b[MAXM], c[MAXM];
int main(){n = readint(); int m = readint();k = readint(); // globalrep(i,1,m){ // inputa[i] = readint(), b[i] = readint();c[i] = readint(); ++ deg[a[i]], ++ deg[b[i]];}rep(i,1,n) g[i] = new PII[deg[i]], g[i] += deg[i];rep(i,1,m){ // link edge*(-- g[a[i]]) = std::make_pair(b[i],c[i]);*(-- g[b[i]]) = std::make_pair(a[i],c[i]);}llong ans = normal(1,n);rep(i,1,m) getMin(ans,check(c[i],1,n));printf("%lld\n",ans);return 0;
}

[CF

题目