某岛

… : "…アッカリ~ン . .. . " .. .
March 15, 2020

BZOJ 2125: 最短路

圆方树。

const int N = int(2e4) + 9, LV = 15;

VII adj[N], adjj[N];
int dfn[N], low[N], tt, sta[N], top;
int fa[LV][N], dep[N], D[N], DD[N], L[N];
int n, nn;

inline int move_up(int x, int t){
    for (int lv=0;t;++lv,t>>=1)
        if (t&1) x = fa[lv][x];
    return x;
}
inline int lca(int x, int y) {
    if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
    DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
    return fa[0][x];
}
void getLCA(int x, int y, int &a, int &b, int &z) {
    if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) {z = x; return;}
    DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
    a = x; b = y; z = fa[0][x];
}

void add_edge(int u, int v, LL w) {
    adjj[u].PB(MP(v, w));
}

#define v it->fi
#define w it->se
void tarjan(int u = 1, int p = -1) {
    low[u] = dfn[u] = ++tt;
    sta[++top] = u;
    ECH(it, adj[u]) if (v != p) {
        if (!dfn[v]) {
            D[v] = D[u] + w; tarjan(v, u);
            checkMin(low[u], low[v]);
            if (dfn[v] == low[v]) add_edge(u, v, w); // tree edge
        } else if (dfn[v] < dfn[u]) { // find circle
            checkMin(low[u], dfn[v]);
            add_edge(v, ++nn, 0); L[nn] = D[u]-D[v]+w;
            for (int i=top;sta[i]!=v;--i) {
                int d = D[sta[i]]-D[v];
                add_edge(nn, sta[i], min(d, L[nn]-d));
            }
        }
    }
    --top;
}
#define p fa[0][u]
void dfs(int u = 1) {
    ECH(it, adjj[u]) {
        dep[v] = dep[u] + 1; DD[v] = DD[u] + w;
        fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
        dfs(v);
    }
}
#undef p
#undef w
#undef v

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    int Q, m; RD(n, m, Q);

    DO(m) {
        int x, y, w; RD(x, y, w);
        adj[x].PB(MP(y, w));
        adj[y].PB(MP(x, w));
    }

    nn = n; tarjan(); dfs();

    DO(Q) {
        int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z);

        //cout << x << " " << y << " " <<  z<< endl;

        if (z <= n) { // round one ...
            OT(DD[x]+DD[y]-DD[z]*2);
        } else { // square one ...
            int d = abs(D[a]-D[b]);
            OT(DD[x]+DD[y]-DD[a]-DD[b]+min(d, L[z]-d));
        }
    }
}

動態仙人掌(BZOJ 會 TLE)

/*
    This code has been written by MinakoKojima, feel free to ask me question. Blog: http://www.shuizilong.com/house
    Template Date: 2015.10.12
    Note: ...
*/

#pragma comment(linker, "/STACK:36777216")
//#pragma GCC optimize ("O2")
#define LOCAL
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>

//#include <tr1/unordered_set>
//#include <tr1/unordered_map>
//#include <array>

using namespace std;

#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define REP_C(i, n) for (int n____=n,i=0;i<n____;++i)
#define FOR_C(i, a, b) for (int b____=b,i=a;i<b____;++i)
#define DWN_C(i, b, a) for (int a____=a,i=b-1;i>=a____;--i)
#define REP_N(i, n) for (i=0;i<n;++i)
#define FOR_N(i, a, b) for (i=a;i<b;++i)
#define DWN_N(i, b, a) for (i=b-1;i>=a;--i)
#define REP_1_C(i, n) for (int n____=n,i=1;i<=n____;++i)
#define FOR_1_C(i, a, b) for (int b____=b,i=a;i<=b____;++i)
#define DWN_1_C(i, b, a) for (int a____=a,i=b;i>=a____;--i)
#define REP_1_N(i, n) for (i=1;i<=n;++i)
#define FOR_1_N(i, a, b) for (i=a;i<=b;++i)
#define DWN_1_N(i, b, a) for (i=b;i>=a;--i)
#define REP_C_N(i, n) for (int n____=(i=0,n);i<n____;++i)
#define FOR_C_N(i, a, b) for (int b____=(i=0,b);i<b____;++i)
#define DWN_C_N(i, b, a) for (int a____=(i=b-1,a);i>=a____;--i)
#define REP_1_C_N(i, n) for (int n____=(i=1,n);i<=n____;++i)
#define FOR_1_C_N(i, a, b) for (int b____=(i=a,b);i<=b____;++i)
#define DWN_1_C_N(i, b, a) for (int a____=(i=b,a);i>=a____;--i)

#define ECH(it, A) for (__typeof((A).begin()) it=(A).begin(); it != (A).end(); ++it)
#define rECH(it, A) for (__typeof((A).rbegin()) it=(A).rbegin(); it != (A).rend(); ++it)
#define REP_S(i, str) for (char*i=str;*i;++i)
#define REP_L(i, hd, suc) for (int i=hd;i;i=suc[i])
#define REP_G(i, u) REP_L(i,hd[u],suc)
#define REP_SS(x, s) for (int x=s;x;x=(x-1)&s)
#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP_2(i, j, n, m) REP(i, n) REP(j, m)
#define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)
#define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
#define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)
#define REP_4(i, j, k, ii, n, m, l, nn) REP(i, n) REP(j, m) REP(k, l) REP(ii, nn)
#define REP_4_1(i, j, k, ii, n, m, l, nn) REP_1(i, n) REP_1(j, m) REP_1(k, l) REP_1(ii, nn)

#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define LBD(A, x) (lower_bound(ALL(A), x) - A.begin())
#define UBD(A, x) (upper_bound(ALL(A), x) - A.begin())
#define CTN(T, x) (T.find(x) != T.end())
#define SZ(A) int((A).size())
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define PTT pair<T, T>
#define Ts *this
#define rTs return Ts
#define fi first
#define se second
#define re real()
#define im imag()

#define Rush for(int ____T=RD(); ____T--;)
#define Display(A, n, m) {                      \
  REP(i, n){                                    \
        REP(j, m-1) cout << A[i][j] << " ";     \
        cout << A[i][m-1] << endl;                \
    }                                            \
}
#define Display_1(A, n, m) {                    \
    REP_1(i, n){                                \
        REP_1(j, m-1) cout << A[i][j] << " ";   \
        cout << A[i][m] << endl;                \
    }                                            \
}

typedef long long LL;
//typedef long double DB;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<string> VS;
typedef vector<LL> VL;
typedef vector<DB> VF;
typedef set<int> SI;
typedef set<string> SS;
typedef map<int, int> MII;
typedef map<string, int> MSI;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

template<class T> inline T& RD(T &);
template<class T> inline void OT(const T &);
//inline int RD(){int x; return RD(x);}
inline LL RD(){LL x; return RD(x);}
inline DB& RF(DB &);
inline DB RF(){DB x; return RF(x);}
inline char* RS(char *s);
inline char& RC(char &c);
inline char RC();
inline char& RC(char &c){scanf(" %c", &c); return c;}
inline char RC(){char c; return RC(c);}
//inline char& RC(char &c){c = getchar(); return c;}
//inline char RC(){return getchar();}

template<class T> inline T& RDD(T &);
inline LL RDD(){LL x; return RDD(x);}

template<class T0, class T1> inline T0& RD(T0 &x0, T1 &x1){RD(x0), RD(x1); return x0;}
template<class T0, class T1, class T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2); return x0;}
template<class T0, class T1, class T2, class T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;}
template<class T0, class T1, class T2, class T3, class T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}
template<class T0, class T1> inline void OT(const T0 &x0, const T1 &x1){OT(x0), OT(x1);}
template<class T0, class T1, class T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2){OT(x0), OT(x1), OT(x2);}
template<class T0, class T1, class T2, class T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);}
template<class T0, class T1, class T2, class T3, class T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}
inline char& RC(char &a, char &b){RC(a), RC(b); return a;}
inline char& RC(char &a, char &b, char &c){RC(a), RC(b), RC(c); return a;}
inline char& RC(char &a, char &b, char &c, char &d){RC(a), RC(b), RC(c), RC(d); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}
inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}
inline DB& RF(DB &a, DB &b){RF(a), RF(b); return a;}
inline DB& RF(DB &a, DB &b, DB &c){RF(a), RF(b), RF(c); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d){RF(a), RF(b), RF(c), RF(d); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}
inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}
inline void RS(char *s1, char *s2){RS(s1), RS(s2);}
inline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);}
template<class T0,class T1>inline T0& RDD(T0&a, T1&b){RDD(a),RDD(b); return a;}
template<class T0,class T1,class T2>inline T1& RDD(T0&a, T1&b, T2&c){RDD(a),RDD(b),RDD(c); return a;}

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}
template<class T> inline void CLR(T &A){A.clear();}

template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);}
template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);}
template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}
template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);}
template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);}
template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}
template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}
template<class T> inline void CLR(priority_queue<T> &Q){while (!Q.empty()) Q.pop();}
template<class T> inline void CLR(stack<T> &S){while (!S.empty()) S.pop();}
template<class T> inline void CLR(queue<T> &Q){while (!Q.empty()) Q.pop();}

template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);}
template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);}
template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}
template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}
template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);}

template<class T> inline bool EPT(T &a){return a.empty();}
template<class T> inline T& SRT(T &A){sort(ALL(A)); return A;}
template<class T, class C> inline T& SRT(T &A, C cmp){sort(ALL(A), cmp); return A;}
template<class T> inline T& RVS(T &A){reverse(ALL(A)); return A;}
template<class T> inline T& UNQQ(T &A){A.resize(unique(ALL(A))-A.begin());return A;}
template<class T> inline T& UNQ(T &A){SRT(A);return UNQQ(A);}
template<class T, class C> inline T& UNQ(T &A, C cmp){SRT(A, cmp);return UNQQ(A);}


//}

/** Constant List .. **/ //{

int MOD = int(1e9) + 7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};

//}

/** Add On .. **/ //{
// <<= '0. Nichi Joo ., //{

template<class T> inline bool checkMin(T &a,const T b){return b < a ? a = b, 1 : 0;}
template<class T> inline bool checkMax(T &a,const T b){return a < b ? a = b, 1 : 0;}
template <class T, class C> inline bool checkUpd(T& a, const T b, C c){return c(b,a) ? a = b, 1 : 0;}
template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);}
template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}
template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}
template<class T> inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}
template<class T> inline T min(T a, T b, T c, T d, T e){return min(min(min(a,b),min(c,d)),e);}
template<class T> inline T max(T a, T b, T c, T d, T e){return max(max(max(a,b),max(c,d)),e);}
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T cub(T a){return a*a*a;}
template<class T> inline T ceil(T x, T y){return (x - 1) / y + 1;}
template<class T> T abs(T x){return x>0?x:-x;}
inline int sgn(DB x){return x < -EPS ? -1 : x > EPS;}
inline int sgn(DB x, DB y){return sgn(x - y);}

inline DB cos(DB a, DB b, DB c){return (sqr(a)+sqr(b)-sqr(c))/(2*a*b);}
inline DB cot(DB x){return 1./tan(x);};
inline DB sec(DB x){return 1./cos(x);};
inline DB csc(DB x){return 1./sin(x);};

//}
// <<= '1. Bitwise Operation ., //{
namespace BO{

inline bool _1(int x, int i){return bool(x&1<<i);}
inline bool _1(LL x, int i){return bool(x&1LL<<i);}
inline LL _1(int i){return 1LL<<i;}
inline LL _U(int i){return _1(i) - 1;};

inline int reverse_bits(int x){
    x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
    x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
    x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
    x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
    x = ((x >>16) & 0x0000ffff) | ((x <<16) & 0xffff0000);
    return x;
}

inline LL reverse_bits(LL x){
    x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
    x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
    x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
    x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
    x = ((x >>16) & 0x0000ffff0000ffffLL) | ((x <<16) & 0xffff0000ffff0000LL);
    x = ((x >>32) & 0x00000000ffffffffLL) | ((x <<32) & 0xffffffff00000000LL);
    return x;
}

template<class T> inline bool odd(T x){return x&1;}
template<class T> inline bool even(T x){return !odd(x);}
template<class T> inline T low_bit(T x) {return x & -x;}
template<class T> inline T high_bit(T x) {T p = low_bit(x);while (p != x) x -= p, p = low_bit(x);return p;}
template<class T> inline T cover_bit(T x){T p = 1; while (p < x) p <<= 1;return p;}
template<class T> inline int cover_idx(T x){int p = 0; while (_1(p) < x ) ++p; return p;}

inline int clz(int x){return __builtin_clz(x);}
inline int clz(LL x){return __builtin_clzll(x);}
inline int ctz(int x){return __builtin_ctz(x);}
inline int ctz(LL x){return __builtin_ctzll(x);}
inline int lg2(int x){return !x ? -1 : 31 - clz(x);}
inline int lg2(LL x){return !x ? -1 : 63 - clz(x);}
inline int low_idx(int x){return !x ? -1 : ctz(x);}
inline int low_idx(LL x){return !x ? -1 : ctz(x);}
inline int high_idx(int x){return lg2(x);}
inline int high_idx(LL x){return lg2(x);}
inline int parity(int x){return __builtin_parity(x);}
inline int parity(LL x){return __builtin_parityll(x);}
inline int count_bits(int x){return __builtin_popcount(x);}
inline int count_bits(LL x){return __builtin_popcountll(x);}

} using namespace BO;//}


// <<= '2. Number Theory .,//{
namespace NT{

inline void INC(int &a, int b){a += b; if (a >= MOD) a -= MOD;}
inline int sum(int a, int b){a += b; if (a >= MOD) a -= MOD; return a;}

/* 模数两倍刚好超 int 时。
inline int sum(uint a, int b){a += b; a %= MOD;if (a < 0) a += MOD; return a;}
inline void INC(int &a, int b){a = sum(a, b);}
*/

inline void DEC(int &a, int b){a -= b; if (a < 0) a += MOD;}
inline int dff(int a, int b){a -= b; if (a < 0) a  += MOD; return a;}
inline void MUL(int &a, int b){a = (LL)a * b % MOD;}
//inline int pdt(int a, int b){return (LL)a * b % MOD;}
inline int pdt(int x,int y) {
    int ret; __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n":"=d"(ret):"a"(x),"b"(y),"c"(MOD));
    return ret;
}


inline int gcd(int m, int n, int &x, int &y){

    x = 1, y = 0; int xx = 0, yy = 1, q;

    while (1){
        q = m / n, m %= n;
        if (!m){x = xx, y = yy; return n;}
        DEC(x, pdt(q, xx)), DEC(y, pdt(q, yy));
        q = n / m, n %= m;
        if (!n) return m;
        DEC(xx, pdt(q, x)), DEC(yy, pdt(q, y));
    }
}

inline int sum(int a, int b, int c){return sum(a, sum(b, c));}
inline int sum(int a, int b, int c, int d){return sum(sum(a, b), sum(c, d));}
inline int pdt(int a, int b, int c){return pdt(a, pdt(b, c));}
inline int pdt(int a, int b, int c, int d){return pdt(pdt(a, b), pdt(c, d));}

inline int pow(int a, LL b){
    int c(1); while (b){
        if (b&1) MUL(c, a);
        MUL(a, a), b >>= 1;
    }
    return c;
}

template<class T> inline T pow(T a, LL b){
    T c(1); while (b){
        if (b&1) c *= a;
        a *= a, b >>= 1;
    }
    return c;
}

template<class T> inline T pow(T a, int b){
    return pow(a, (LL)b);
}

inline int _I(int b){
    int a = MOD, x1 = 0, x2 = 1, q; while (1){
        q = a / b, a %= b;
        if (!a) return x2;
        DEC(x1, pdt(q, x2));

        q = b / a, b %= a;
        if (!b) return x1;
        DEC(x2, pdt(q, x1));
    }
}

inline void DIV(int &a, int b){MUL(a, _I(b));}
inline int qtt(int a, int b){return pdt(a, _I(b));}

struct Int{
    int val;

    operator int() const{return val;}

    Int(int _val = 0):val(_val){
        val %= MOD; if (val < 0) val += MOD;
    }
    Int(LL _val):val(_val){
        _val %= MOD; if (_val < 0) _val += MOD;
        val = _val;
    }

    Int& operator +=(const int& rhs){INC(val, rhs);rTs;}
    Int operator +(const int& rhs) const{return sum(val, rhs);}
    Int& operator -=(const int& rhs){DEC(val, rhs);rTs;}
    Int operator -(const int& rhs) const{return dff(val, rhs);}
    Int& operator *=(const int& rhs){MUL(val, rhs);rTs;}
    Int operator *(const int& rhs) const{return pdt(val, rhs);}
    Int& operator /=(const int& rhs){DIV(val, rhs);rTs;}
    Int operator /(const int& rhs) const{return qtt(val, rhs);}
    Int operator-()const{return MOD-*this;}
};

} using namespace NT;//}


//}



/** I/O Accelerator Interface .. **/ //{
#define g (c=getchar())
#define d isdigit(g)
#define p x=x*10+c-'0'
#define n x=x*10+'0'-c
#define pp l/=10,p
#define nn l/=10,n
template<class T> inline T& RD(T &x){
    char c;while(!d);x=c-'0';while(d)p;
    return x;
}
template<class T> inline T& RDD(T &x){
    char c;while(g,c!='-'&&!isdigit(c));
    if (c=='-'){x='0'-g;while(d)n;}
    else{x=c-'0';while(d)p;}
    return x;
}
inline DB& RF(DB &x){
    //scanf("%lf", &x);
    char c;while(g,c!='-'&&c!='.'&&!isdigit(c));
    if(c=='-')if(g=='.'){x=0;DB l=1;while(d)nn;x*=l;}
        else{x='0'-c;while(d)n;if(c=='.'){DB l=1;while(d)nn;x*=l;}}
    else if(c=='.'){x=0;DB l=1;while(d)pp;x*=l;}
        else{x=c-'0';while(d)p;if(c=='.'){DB l=1;while(d)pp;x*=l;}}
    return x;
}
#undef nn
#undef pp
#undef n
#undef p
#undef d
#undef g
inline char* RS(char *s){
    //gets(s);
    scanf("%s", s);
    return s;
}

LL last_ans; int Case; template<class T> inline void OT(const T &x){
    //printf("Case #%d: ", ++Case);
    //printf("%lld\n", x);
    //printf("%I64d\n", x);
    //printf("%.9f\n", x);
    //printf("%d\n", x);
    cout << x << endl;
    //last_ans = x;
}


//}/* .................................................................................................................................. */

const int MaxN = 10000 + 9;
 
inline int getint()
{
    char c;
    while (c = getchar(), '0' > c || c > '9');
 
    int res = c - '0';
    while (c = getchar(), '0' <= c && c <= '9')
        res = res * 10 + c - '0';
    return res;
}
 
template <class T>
class BlockAllocator
{
private:
    static const int BlockL = 10000;
 
    union TItem
    {
        char rt[sizeof(T)];
        TItem *next;
    };
 
    TItem *pool, *tail;
    TItem *unused;
public:
    BlockAllocator()
    {
        pool = NULL;
        unused = NULL;
    }
 
    T *allocate()
    {
        TItem *p;
        if (unused)
        {
            p = unused;
            unused = unused->next;
        }
        else
        {
            if (pool == NULL)
                pool = new TItem[BlockL], tail = pool;
            p = tail++;
            if (tail == pool + BlockL)
                pool = NULL;
        }
        return (T*)p;
    }
    void deallocate(T *pt)
    {
        TItem *p = (TItem*)pt;
        p->next = unused, unused = p;
    }
};
 
struct edge
{
    int v, u, w;
    int totL;
};
struct lct_edge
{
    int w;
    edge *cirE;
 
    edge *getCirE()
    {
        return this ? this->cirE : NULL;
    }
};
 
struct lct_message
{
    int headL, midL, tailL;
 
    lct_edge *firstE, *lastE;
 
    bool hasCirE;
 
    void rev()
    {
        swap(firstE, lastE);
        swap(headL, tailL);
    }
    void coverCirE(edge *e, bool isSingle)
    {
        hasCirE = isSingle ? false : e != NULL;
    }
 
    friend inline lct_message operator+(const lct_message &lhs, const lct_message &rhs)
    {
        lct_message res;
        res.firstE = lhs.firstE, res.lastE = rhs.lastE;
 
        assert(lhs.lastE == rhs.firstE);
        lct_edge *e = lhs.lastE;
        res.hasCirE = lhs.hasCirE || e->cirE || rhs.hasCirE;
        if (lhs.tailL != -1 && rhs.headL != -1)
        {
            res.headL = lhs.headL;
            res.tailL = rhs.tailL;
            int trL = lhs.tailL + e->w + rhs.headL;
            res.midL = lhs.midL + min(trL, e->cirE->totL - trL) + rhs.midL;
        }
        else if (lhs.tailL != -1)
        {
            res.headL = lhs.headL;
            res.tailL = lhs.tailL + e->w + rhs.midL;
            res.midL = lhs.midL;
        }
        else if (rhs.headL != -1)
        {
            res.headL = lhs.midL + e->w + rhs.headL;
            res.tailL = rhs.tailL;
            res.midL = rhs.midL;
        }
        else
        {
            res.headL = lhs.headL;
            res.tailL = rhs.tailL;
            res.midL = lhs.midL + e->w + rhs.midL;
        }
 
        return res;
    }
};
 
struct lct_node
{
    lct_node *fa, *lc, *rc;
 
    lct_edge *prevE, *nextE;
    
    lct_message msg;
 
    bool hasRev;
    bool hasCoveredCirE;
    edge *coveredCirE;
 
    bool isRoot()
    {
        return !fa || (fa->lc != this && fa->rc != this);
    }
 
    void rotate()
    {
        lct_node *x = this, *y = x->fa, *z = y->fa;
        lct_node *b = x == y->lc ? x->rc : x->lc;
        x->fa = z, y->fa = x;
        if (b)
            b->fa = y;
        if (z)
        {
            if (y == z->lc)
                z->lc = x;
            else if (y == z->rc)
                z->rc = x;
        }
        if (x == y->lc)
            x->rc = y, y->lc = b;
        else
            x->lc = y, y->rc = b;
        y->update();
    }
    void allFaTagDown()
    {
        int anc_n = 0;
        static lct_node *anc[MaxN];
 
        anc[anc_n++] = this;
        for (int i = 0; !anc[i]->isRoot(); i++)
            anc[anc_n++] = anc[i]->fa;
        for (int i = anc_n - 1; i >= 0; i--)
            anc[i]->tag_down();
    }
    void splay()
    {
        allFaTagDown();
        while (!this->isRoot())
        {
            if (!fa->isRoot())
            {
                if ((fa->fa->lc == fa) == (fa->lc == this))
                    fa->rotate();
                else
                    this->rotate();
            }
            this->rotate();
        }
        this->update();
    }
    void splay_until(lct_node *target)
    {
        allFaTagDown();
        while (this->fa != target)
        {
            if (fa->fa != target)
            {
                if ((fa->fa->lc == fa) == (fa->lc == this))
                    fa->rotate();
                else
                    this->rotate();
            }
            this->rotate();
        }
        lct_node *x = this;
        while (!x->isRoot())
            x->update(), x = x->fa;
        x->update();
    }
 
    lct_node *lmost()
    {
        lct_node *x = this;
        while (x->tag_down(), x->lc)
            x = x->lc;
        return x;
    }
 
    void access()
    {
        for (lct_node *p = this, *q = NULL; p; q = p, p = p->fa)
        {
            p->splay();
            p->nextE = q ? q->msg.firstE : NULL;
            p->rc = q;
        }
        this->splay();
    }
    void makeRoot()
    {
        this->access();
        this->tag_rev();
        this->tag_down();
    }
    lct_node *findRoot()
    {
        this->access();
        lct_node *root = this->lmost();
        root->splay();
        return root;
    }
 
    void tag_rev()
    {
        hasRev = !hasRev;
        msg.rev();
    }
    void tag_coverCirE(edge *e)
    {
        hasCoveredCirE = true, coveredCirE = e;
        msg.coverCirE(e, !lc && !rc);
    }
    void tag_down()
    {
        if (hasRev)
        {
            swap(lc, rc);
            swap(prevE, nextE);
 
            if (lc)
                lc->tag_rev();
            if (rc)
                rc->tag_rev();
            hasRev = false;
        }
        if (hasCoveredCirE)
        {
            if (lc)
            {
                prevE->cirE = coveredCirE;
                lc->tag_coverCirE(coveredCirE);
            }
            if (rc)
            {
                nextE->cirE = coveredCirE;
                rc->tag_coverCirE(coveredCirE);
            }
            hasCoveredCirE = false;
        }
    }
    void update()
    {
        if (prevE->getCirE() == nextE->getCirE())
            msg.headL = msg.tailL = -1;
        else
        {
            msg.headL = prevE->getCirE() ? 0 : -1;
            msg.tailL = nextE->getCirE() ? 0 : -1;
        }
 
        msg.midL = 0;
 
        msg.hasCirE = false;
        msg.firstE = prevE, msg.lastE = nextE;
 
        if (lc)
            this->msg = lc->msg + this->msg;
        if (rc)
            this->msg = this->msg + rc->msg;
    }
};
 
lct_node lctVer[MaxN + 1];
BlockAllocator<edge> lctCirEAllocator;
BlockAllocator<lct_edge> lctEAllocator;
 
int n;
 
void cactus_init()
{
    for (int v = 1; v <= n; v++)
    {
        lct_node *p = lctVer + v;
        p->fa = p->lc = p->rc = NULL;
        p->prevE = p->nextE = NULL;
 
        p->hasRev = false;
        p->hasCoveredCirE = false;
 
        p->update();
    }
}
 
bool cactus_link(int v, int u, int w)
{
    if (v == u)
        return false;
    if (v > u)
        swap(v, u);
 
    lct_node *x = lctVer + v, *y = lctVer + u;
 
    x->makeRoot();
    y->makeRoot();
 
    if (x->fa)
    {
        x->access();
        y->splay_until(x);
        if (x->msg.hasCirE)
            return false;
        edge *cirE = lctCirEAllocator.allocate();
        cirE->v = v, cirE->u = u, cirE->w = w;
        cirE->totL = x->msg.midL + w;
 
        y->nextE->cirE = cirE;
        x->prevE->cirE = cirE;
        if (y->rc)
            y->rc->tag_coverCirE(cirE);
        y->update(), x->update();
    }
    else
    {
        x->fa = y;
 
        lct_edge *e = lctEAllocator.allocate();
        e->w = w, e->cirE = NULL;
        x->prevE = e;
        x->update();
    }
    return true;
}
bool cactus_cut(int v, int u, int w)
{
    if (v == u)
        return false;
    if (v > u)
        swap(v, u);
 
    lct_node *x = lctVer + v, *y = lctVer + u;
 
    if (x->findRoot() != y->findRoot())
        return false;
 
    y->makeRoot();
    x->access();
    y->splay_until(x);
 
    lct_edge *e = y->nextE;
    edge *cirE = e->cirE;
 
    if (cirE && cirE->v == v && cirE->u == u && cirE->w == w)
    {
        y->nextE->cirE = NULL;
        x->prevE->cirE = NULL;
        if (y->rc)
            y->rc->tag_coverCirE(NULL);
        y->update(), x->update();
 
        lctCirEAllocator.deallocate(cirE);
 
        return true;
    }
    if (!y->rc && e->w == w)
    {
        if (cirE)
        {
            y->nextE->cirE = NULL;
            x->prevE->cirE = NULL;
        }
 
        y->nextE = NULL, x->prevE = NULL;
 
        lctEAllocator.deallocate(e);
        
        x->lc = NULL, y->fa = NULL;
        x->update(), y->update();
 
        if (cirE)
        {
            lct_node *ex = lctVer + cirE->v;
            lct_node *ey = lctVer + cirE->u;
 
            lct_node *rx = ex->findRoot();
            lct_node *ry = ey->findRoot();
            if (rx != ex)
            {
                ex->access();
                rx->splay_until(ex);
 
                ex->prevE->cirE = NULL;
                rx->nextE->cirE = NULL;
                if (rx->rc)
                    rx->rc->tag_coverCirE(NULL);
                rx->update(), ex->update();
            }
 
            if (ry != ey)
            {
                ey->access();
                ry->splay_until(ey);
 
                ey->prevE->cirE = NULL;
                ry->nextE->cirE = NULL;
                if (ry->rc)
                    ry->rc->tag_coverCirE(NULL);
                ry->update(), ey->update();
            }
 
            ex->makeRoot(), ey->makeRoot();
 
            ex->fa = ey;
 
            e = lctEAllocator.allocate();
            e->w = cirE->w, e->cirE = NULL;
            ex->prevE = e, ex->update();
 
            lctCirEAllocator.deallocate(cirE);
        }
        return true;
    }
    return false;
}
int cactus_query(int qv, int qu)
{
    lct_node *x = lctVer + qv, *y = lctVer + qu;
    if (x->findRoot() != y->findRoot())
        return -1;
 
    x->makeRoot();
    y->access();
    return y->msg.midL;
}

struct Edge {
    int x, y, w;
    Edge(int x, int y, int w):x(x),y(y),w(w) {
    }
    void link() {
        cactus_link(x, y, w);
    }
}; vector<Edge> E;

const int N = MaxN;
VII adj[N];
int dfn[N], nn;

void dfs(int u = 1, int p = 0) {
    dfn[u] = ++nn;
   // for (auto e: adj[u]) {
     //   int v = e.fi, w = e.se;
    ECH(it, adj[u]) {
        int v= it->fi, w = it->se;
        if (v == p) continue;
        if (dfn[v]) {
            E.PB(Edge(u,v,w));
        } else {
            lct_node *y = lctVer + u;
            lct_node *x = lctVer + v;
            
            //vv->fa = uu;
            E.PB(Edge(u,v,w));
            
            /*
                   x->fa = y;
            
                   lct_edge *e = lctEAllocator.allocate();
                   e->w = w, e->cirE = NULL;
                   x->prevE = e;*/
                  // x->update();
            
            
            dfs(v, u);
        }
    }
}
 
int main()
{
    int nQ, m;
 
    cin >> n >> m >> nQ;
    cactus_init();
    
    DO(m) {
        int v = getint(), u = getint(), w = getint();
        adj[v].PB({u,w});
         adj[u].PB({v,w});
    }
    
    dfs(); //for(auto e: E) e.link();
    ECH(it, E) it->link();
    
    DO(nQ) {
        int v = getint(), u = getint();
        printf("%d\n", cactus_query(v, u));
    }
}