记录编号	91527	评测结果	AAAAAAAAAA
题目名称	假期旅行计划	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.220 s
提交时间	2014-03-15 11:23:25	内存使用	32.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const ll INF=1e17;
const int SIZEN=20010,SIZEK=210;
int hublis[SIZEK]={0},hubid[SIZEN]={0};
bool ishub[SIZEN]={0};
vector<pair<int,int> > c[SIZEN];
int N,M,K,Q;
ll dist[SIZEK][SIZEN]={0};
ll ablenum=0,costsum=0;//能满足的购票数和总花费
void request(int a,int b){//从a到b
	if(ishub[a]){
		if(dist[hubid[a]][b]!=INF){
			ablenum++;
			costsum+=dist[hubid[a]][b];
		}
	}
	else{
		ll mc=INF;
		for(int i=0;i<c[a].size();i++){
			int u=c[a][i].first;
			if(!ishub[u]){
				if(u!=a) cout<<"error!"<<endl;
				continue;
			}
			mc=min(mc,dist[hubid[u]][b]+c[a][i].second);
		}
		if(mc!=INF){
			ablenum++;
			costsum+=mc;
		}
	}
}
void answer(void){
	int a,b;
	while(Q--){
		scanf("%d%d",&a,&b);
		request(a,b);
	}
	printf("%lld\n%lld\n",ablenum,costsum);
}
void SPFA(vector<pair<int,int> > c[SIZEN],ll f[],int s){
	for(int i=1;i<=N;i++) f[i]=INF;
	queue<int> Q;
	bool inq[SIZEN]={0};
	f[s]=0,inq[s]=true,Q.push(s);
	while(!Q.empty()){
		int u=Q.front();Q.pop();inq[u]=false;
		for(int i=0;i<c[u].size();i++){
			int v=c[u][i].first;
			if(f[v]>f[u]+c[u][i].second){
				f[v]=f[u]+c[u][i].second;
				if(!inq[v]){
					inq[v]=true;
					Q.push(v);
				}
			}
		}
	}
}
void read(void){
	scanf("%d%d%d%d",&N,&M,&K,&Q);
	int u,v,w;
	for(int i=1;i<=M;i++){
		scanf("%d%d%d",&u,&v,&w);
		c[u].push_back(make_pair(v,w));
	}
	for(int i=1;i<=N;i++) c[i].push_back(make_pair(i,0));
	for(int i=1;i<=K;i++) scanf("%d",&hublis[i]),ishub[hublis[i]]=true,hubid[hublis[i]]=i;
}
int main(){
	freopen("vacationgold.in","r",stdin);
	freopen("vacationgold.out","w",stdout);
	read();
	for(int i=1;i<=K;i++) SPFA(c,dist[i],hublis[i]);
	answer();
	return 0;
}