BZOJ 1706权限题。
倍增$floyd$。
首先这道题有用的点最多只有$200$个，先离散化。
设$f_{p, i, j}$表示经过$2^p$条边从$i$到$j$的最短路，那么有转移$f_{p, i, j} = min(f_{p - 1, i, k} + f_{p - 1, k, j})$。
然后做一个类似于快速幂的东西把$n$二进制拆分然后把当前的$f$代进去转移。
可以设一个$g_{i, j}$表示当前从$i$到$j$的最短路，为了保证转移顺序的正确，可以把$g$抄出来到$h$中，然后用$g_{i, j} = min(h_{i, k} + f_{p, k, j})$转移。
时间复杂度$O(m^3logn)$。
Code：
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll; const int N = ;
const int M = 1e6 + ;
const int Lg = ; int n, m, cnt = , id[M];
ll f[Lg][N][N], g[N][N], h[N][N]; template <typename T>
inline void read(T &X) {
X = ; char ch = ; T op = ;
for(; ch > '' || ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline int getId(int now) {
if(!id[now]) id[now] = ++cnt;
return id[now];
} template <typename T>
inline void chkMin(T &x, T y) {
if(y < x) x = y;
} inline void mul(int p) {
for(int i = ; i <= cnt; i++)
for(int j = ; j <= cnt; j++)
h[i][j] = g[i][j]; memset(g, 0x3f, sizeof(g));
for(int k = ; k <= cnt; k++)
for(int i = ; i <= cnt; i++)
for(int j = ; j <= cnt; j++)
chkMin(g[i][j], h[i][k] + f[p][k][j]);
} int main() {
// freopen("2.in", "r", stdin); int st, ed;
read(n), read(m), read(st), read(ed);
st = getId(st), ed = getId(ed); memset(f, 0x3f, sizeof(f));
for(int i = ; i <= m; i++) {
int x, y; ll v;
read(v), read(x), read(y);
x = getId(x), y = getId(y);
chkMin(f[][x][y], v), chkMin(f[][y][x], v);
} for(int p = ; p <= ; p++)
for(int k = ; k <= cnt; k++)
for(int i = ; i <= cnt; i++)
for(int j = ; j <= cnt; j++)
chkMin(f[p][i][j], f[p - ][i][k] + f[p - ][k][j]); memset(g, 0x3f, sizeof(g));
for(int i = ; i <= cnt; i++) g[i][i] = 0LL;
for(int tmp = n, p = ; tmp > ; tmp >>= ) {
if(tmp & ) mul(p);
++p;
} printf("%lld\n", g[st][ed]);
return ;
}