记录编号	90850	评测结果	AAATTEEEEE
题目名称	假期旅行计划	最终得分	30
用户昵称	请叫我“读者”	是否通过	未通过
代码语言	C++	运行时间	4.214 s
提交时间	2014-03-10 12:48:03	内存使用	0.32 MiB

/*
King_CH_Designed
on 2014/3/7
*/
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const long long oo=(2<<62);
vector<vector<long long> >A;
vector<bool>TF;
vector<vector<pair<long long,long long> > >E;
inline long long Djs(long long,long long);
long long n,m,k,q;
int main()
{
	long long i,j,p,x,y,num=0,Ans=0;
	freopen("vacationgold.in","r",stdin);
	freopen("vacationgold.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m>>k>>q;
	A.resize(n);E.resize(n);TF.resize(n,false);
	for(i=0;i<n;i++)
	{
		A[i].resize(n);
		for(j=0;j<n;j++)A[i][j]=oo;
		A[i][i]=0;
	}
	for(i=0;i<m;i++)
	{
		cin>>x>>y>>p;
		E[x-1].push_back(make_pair(p,y-1));
	}
	for(i=0;i<k;i++)
	{
		cin>>x;
		TF[x-1]=true;
	}
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(i!=j)A[i][j]=Djs(i,j);
	for(i=0;i<q;i++)
	{
		cin>>x>>y;
		if(A[x-1][y-1]!=oo)
		{
			num++;
			Ans+=A[x-1][y-1];
		}
	}
	cout<<num<<endl<<Ans;
	return 0;
}
inline long long Djs(long long s,long long e)
{
	priority_queue<pair<long long,pair<long long,bool> >,vector<pair<long long,pair<long long,bool> > >,greater<pair<long long,pair<long long,bool> > > >Q;
	Q.push(make_pair(0,make_pair(s,TF[s])));
	vector<bool>v(n,false);
	long long pos,Len,i;
	bool Sg;
	while(!Q.empty())
	{
		Len=Q.top().first;
		pos=Q.top().second.first;
		Sg=Q.top().second.second;
		Q.pop();
		if(pos==e)
		{
			if(Sg==false)
				goto CH;
			else
				return Len;
		}
		if(v[pos]==false)
		{
			v[pos]=true;
			for(i=0;i<E[pos].size();i++)
				if(v[E[pos][i].second]==false)
					Q.push(make_pair(Len+E[pos][i].first,make_pair(E[pos][i].second,Sg|TF[E[pos][i].second])));
		}
		CH:;
	}
	return oo;
}