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

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
const long long INF=20000*10001;
vector <pair<int,long long> > p[20001];
vector <pair<int,long long> > q[20001];//reversal p
int N,M,K,Q,bottom[201];
long long key[20001];
bool boo[20010];
long long dis[201][20001],ver[20001][201];
int main()
{
	freopen("vacationgold.in","r",stdin);
	freopen("vacationgold.out","w",stdout);
	scanf("%d%d%d%d",&N,&M,&K,&Q);
	int u,v,d;
	for(int i=1;i<=M;i++)
	{
		scanf("%d%d%d",&u,&v,&d);
		p[u].push_back(make_pair(v,d));
		q[v].push_back(make_pair(u,d));
	}
	//=================================
	/*for(int i=1;i<=N;i++)
	{
		for(int j=0;j<p[i].size();j++)
			printf("%d %d\n",p[i][j].first,p[i][j].second);
		printf("\n");
	}*/
	//========================================================
	deque <int> Que;
	for(int i=1;i<=K;i++)
	{
		scanf("%d",&bottom[i]);
		//======================
		for(int j=1;j<=N;j++)key[j]=INF;
		memset(boo,0,sizeof(boo));
		Que.clear();
		Que.push_back(bottom[i]);
		key[bottom[i]]=0;
		boo[bottom[i]]=1;
		while(!Que.empty())
		{
			u=Que.front();
			Que.pop_front();
			boo[u]=0;
			for(unsigned int j=0;j<p[u].size();j++)
			{
				v=p[u][j].first;
				d=p[u][j].second;
				if(key[v]<=key[u]+d)continue;
				key[v]=key[u]+d;
				if(boo[v])continue;
				boo[v]=1;
				Que.push_back(v);
			}
		}
		for(int j=1;j<=N;j++)
			dis[i][j]=key[j];//the shortest path of bottom[i] to j
		/*for(int j=1;j<=N;j++)
			printf("%d ",key[j]);
		printf("\n");*/
		//=========================================
		for(int j=1;j<=N;j++)key[j]=INF;
		memset(boo,0,sizeof(boo));
		Que.clear();
		Que.push_back(bottom[i]);
		key[bottom[i]]=0;
		boo[bottom[i]]=1;
		while(!Que.empty())
		{
			u=Que.front();
			Que.pop_front();
			boo[u]=0;
			for(unsigned int j=0;j<q[u].size();j++)
			{
				v=q[u][j].first;
				d=q[u][j].second;
				if(key[v]<=key[u]+d)continue;
				key[v]=key[u]+d;
				if(boo[v])continue;
				boo[v]=1;
				Que.push_back(v);
			}
		}
		for(int j=1;j<=N;j++)
			ver[j][i]=key[j];//the shortest path of j to bottom[i]
		/*for(int j=1;j<=N;j++)
			printf("%d ",key[j]);
		printf("\n");*/
	}
	//==========================================
	/*for(int i=1;i<=K;i++)
	{
		for(int j=1;j<=N;j++)
		{
			printf("%d\n",dis[i][j]);
			printf("%d\n",ver[j][i]);
		}
		printf("\n");
	}*/
	//==========================================
	int a,b,ans=0;
	long long Ans=0,temp;
	bool able;
	for(int i=1;i<=Q;i++)
	{
		scanf("%d%d",&a,&b);
		able=false;
		temp=INF;
		for(int j=1;j<=K;j++)
		{
			if(ver[a][j]!=INF&&dis[j][b]!=INF)//using bottom[i]
			{
				able=true;
				temp=min(temp,ver[a][j]+dis[j][b]);
			}
		}
		if(able)
		{
			ans++;
			Ans+=temp;
		}
		//printf("%d\n%lld\n",ans,Ans);
	}
	printf("%d\n%lld\n",ans,Ans);
	return 0;
}