题目描述
有N(1 <= N <= 200)个农场，用1..N编号。航空公司计划在农场间建立航线。对于任意一条航线，选择农场1..K中的农场作为枢纽(1 <= K <= 100, K <= N)。
当前共有M (1 <= M <= 10,000)条单向航线连接这些农场，从农场u_i 到农场 v_i, 将花费 d_i美元。(1 <= d_i <= 1,000,000).
航空公司最近收到Q (1 <= Q <= 10,000)个单向航行请求。第i个航行请求是从农场a_i到农场 b_i，航行必须经过至少一个枢纽农场（可以是起点或者终点农场），因此可能会多次经过某些农场。
请计算可行航行请求的数量，及完成所有可行请求的总费用。
输入输出格式
输入格式：
Line 1: Four integers: N, M, K, and Q.Lines 2..1+M: Line i+1 contains u_i, v_i, and d_i for flight i.
Lines 2+M..1+M+Q: Line 1+M+i describes the ith trip in terms of a_i and b_i
输出格式：
Line 1: The number of trips (out of Q) for which a valid route is possible.
Line 2: The sum, over all trips for which a valid route is possible, of the minimum possible route cost.
输入输出样例
输入样例#1：
3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2
输出样例#1：
2
24
说明
There are three farms (numbered 1..3); farm 1 is a hub. There is a $10 flight from farm 3 to farm 1, and so on. We wish to look for trips from farm 3 to farm 2, from 2->3, and from 1->2.
The trip from 3->2 has only one possible route, of cost 10+7. The trip from 2->3 has no valid route, since there is no flight leaving farm 2. The trip from 1->2 has only one valid route again, of cost 7.
floyd求最短路，有些卡题面。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=205;
int n,m,k,cnt,q,f[205][205];
long long ans;
int main()
{scanf("%d%d%d%d",&n,&m,&k,&q);memset(f,0x3f,sizeof(f));for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);f[x][y]=min(f[x][y],z);}for(int g=1;g<=n;g++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)f[i][j]=0;elsef[i][j]=min(f[i][j],f[i][g]+f[g][j]);}while(q--){int x,y;scanf("%d%d",&x,&y);int res=1e9+7;for(int i=1;i<=k;i++)res=min(res,f[x][i]+f[i][y]);if(res<=1e9){cnt++;ans+=res;}}printf("%d\n%lld\n",cnt,ans);return 0;
}