Description
给定一张图，(n) 个点，(m) 条单向边。
每条单向边至少有一个端点是枢纽，总共有 (k) 个枢纽。
给出若干对形如 x y 的询问，表示询问能否从 (x) 点走到到 (y) 点。
求出能成立的询问的个数，以及所有询问的最短路程和。
Solution
发现如果每个点都跑一遍最短路，问题就可以直接解决。
但是 (nle 20000)，数组显然开不下。
另外有路径必须经过至少一个枢纽的限制，所以只对起点跑最短路也是行不通的。
已知每条边的至少一个端点为枢纽，且最多 (k) 个，(kle 200)。
所以我们对每个枢纽跑一遍最短路，就可以掌握全图的情况。
对于每组询问：
-
如果起点是枢纽，已经跑过最短路了，可以直接判断。
-
如果起点不是枢纽，那么其能遍历到的点一定是枢纽，而对于枢纽已经处理完毕，所以可以取起点到枢纽的边权与枢纽到终点的最短路之和的最小值。
另外注意，虽然 (kle 200)，但是给出的枢纽编号范围是 ([1,20000])，如果直接将其编号作为数组的一维会开不下。
根据以上信息，本题可以完成。
Code
#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define maxn 40010
#define INF 0x3f3f3f3f
#define int long long
using namespace std;
bool vis[maxn];
int n,m,k,q,tot,ans,cnt,pre[maxn];
int Dis[maxn],head[maxn],path[210][maxn];
struct edge{int fr,to,dis,nxt;}e[maxn];
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
return s*w;
}
void add(int fr,int to,int dis){
e[++tot]=(edge){fr,to,dis,head[fr]};head[fr]=tot;
}
void Dijk(int s){
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
memset(Dis,INF,sizeof Dis);memset(vis,0,sizeof vis);q.push(make_pair(0,s));Dis[s]=0;
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int to=e[i].to;
if(Dis[to]>Dis[u]+e[i].dis)
Dis[to]=Dis[u]+e[i].dis,
q.push(make_pair(Dis[to],to));
}
}
for(int i=1;i<=n;i++) path[pre[s]][i]=Dis[i];
}
signed main(){
memset(path,INF,sizeof path);
n=read();m=read();k=read();q=read();
for(int i=1,fr,to,dis;i<=m;i++){
fr=read();to=read();dis=read();
add(fr,to,dis);
}
for(int i=1,pos;i<=k;i++)
pos=read(),pre[pos]=i,Dijk(pos);
for(int i=1,fr,to;i<=q;i++){
fr=read();to=read();
if(pre[fr]&&path[pre[fr]][to]<path[0][0]) cnt++,ans+=path[pre[fr]][to];
else{
int now=INF;
for(int j=head[fr];j;j=e[j].nxt){
int v=e[j].to;
now=min(e[j].dis+path[pre[v]][to],now);
}
if(now!=INF&&now<path[0][0]) ans+=now,cnt++;
}
}
printf("%lld
%lld",cnt,ans);
return 0;
}