题目链接:https://www.luogu.org/problemnew/show/P3094

题解:做一遍floyd,然后 枚举所有询问,对于每个询问枚举所有k点取dis[u][i]+dis[i][v]dis[u][i] + dis[i][v]的最小值即可

#include <bits/stdc++.h>
#define pa pair<ll, ll>
#define mp make_pair
#define lowbit(x) ((x)&(-x))
#define mem(i, a) memset(i, a, sizeof(i))
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 205 + 5;
ll dis[MAXN][MAXN];
ll n,m,k,q;
int main() {
    cin >> n >> m >> k >> q;
    mem(dis, INF);
    for(ll i = 1; i <= m; i++) {
        ll u,v,w;
        scanf("%lld %lld %lld", &u, &v, &w);
        dis[u][v] = min(dis[u][v], w);
    }
    for(int i = 1; i <= k; i++) dis[i][i] = 0;
    for(ll i = 1; i <= n; i++) {
        for(ll j = 1; j <= n; j++)
            for(ll l = 1; l <= n; l++) {
                dis[j][l] = min(dis[j][l], dis[j][i] + dis[i][l]);
            }
                
    }
    ll ans = 0, tot = 0;
    
    for(ll i = 1; i <= q; i++) {
        ll u,v;
        cin >> u >> v;
        ll now = INF;
        int flag = 0;
        for(int j = 1; j <= k; j++) {
            if(dis[u][j] >= 10000000000 || dis[j][v] >= 10000000000) continue;
            now = min(dis[u][j] + dis[j][v], now);
            flag = 1;
        }
        if(flag)
        ans += now ,tot++;
    }
    cout << tot << '\n' << ans;
    return 0;
}