比赛 20140307 评测结果 AWWWWWWTTT
题目名称 假期旅行计划 最终得分 10
用户昵称 cstdio 运行时间 3.700 s
代码语言 C++ 内存使用 1.66 MiB
提交时间 2014-03-07 21:25:13
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<deque>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
const int SIZEN=20010,SIZEK=210;
const ll INF=1e17;
int hublis[SIZEK]={0};
int hubid[SIZEN]={0};
ll hubdist[SIZEK][SIZEK]={0};
vector<pair<int,int> > c[SIZEN];
vector<pair<int,int> > ct[SIZEN];
vector<pair<int,int> > hc[SIZEN];
vector<pair<int,int> > hct[SIZEN];
bool ishub[SIZEN]={0};
int N,M,K,Q;
ll ans=0;
int satisfac=0;
void check(int a,int b){
	//cout<<a<<" "<<b<<endl;
	ll nowmin=INF;
	for(int i=0;i<hc[a].size();i++){
		for(int j=0;j<hct[b].size();j++){
			//cout<<hubid[c[a][i].first]<<" "<<
			//cout<<a<<" "<<hublis[hc[a][i].first]<<" "<<hublis[hct[b][j].first]<<" "<<b<<endl;
			nowmin=min(nowmin,hc[a][i].second+hubdist[hc[a][i].first][hct[b][j].first]+hct[b][j].second);
		}
	}
	//cout<<a<<" "<<b<<" "<<nowmin<<endl;
	if(nowmin!=INF) satisfac++,ans+=nowmin;
}
void floyd(void){
	for(int i=1;i<=K;i++) for(int j=1;j<=K;j++) hubdist[i][j]=INF;
	for(int i=1;i<=K;i++) hubdist[i][i]=0;
	for(int i=1;i<=K;i++){
		int u=hublis[i];
		for(int j=0;j<c[u].size();j++){
			hubdist[i][hubid[c[u][j].first]]=c[u][j].second;
		}
	}
	for(int i=1;i<=K;i++){
		for(int j=0;j<c[i].size();j++){
			int v=c[i][j].first;
			//cout<<hublis[i]<<" "<<v<<endl;
			if(!ishub[v]){
				for(int k=0;k<c[v].size();k++){
					//cout<<hublis[i]<<" "<<v<<" "<<k<<endl;
					if(ishub[c[v][k].first]){
						//cout<<hublis[i]<<" "<<v<<" "<<c[v][k].first<<endl;
						hubdist[i][hubid[c[v][k].first]]=min(hubdist[i][hubid[c[v][k].first]],(ll)c[i][j].second+(ll)c[v][k].second);
					}
				}
			}
		}
	}
	for(int k=1;k<=K;k++){
		for(int i=1;i<=K;i++){
			for(int j=1;j<=K;j++) hubdist[i][j]=min(hubdist[i][j],hubdist[i][k]+hubdist[k][j]);
		}
	}
	//for(int i=1;i<=K;i++) cout<<hubdist[i][
}
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));
		ct[v].push_back(make_pair(u,w));
		//cout<<u<<" "<<v<<endl;
	}
	for(int i=1;i<=N;i++){
		c[i].push_back(make_pair(i,0));
		ct[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;
	}
	for(int i=1;i<=N;i++){
		for(int j=0;j<c[i].size();j++){
			//cout<<i<<" "<<c[i][j].first<<endl;
			if(ishub[c[i][j].first]){
				//cout<<i<<" "<<c[i][j].first<<endl;
				v=hubid[c[i][j].first];
				hc[i].push_back(make_pair(v,c[i][j].second));
			}
		}
	}
	for(int i=1;i<=N;i++){
		for(int j=0;j<ct[i].size();j++){
			//cout<<i<<" "<<c[i][j].first<<endl;
			if(ishub[ct[i][j].first]){
				v=hubid[ct[i][j].first];
				hct[i].push_back(make_pair(v,ct[i][j].second));
			}
		}
	}
}
void work(void){
	int a,b;
	while(Q--){
		scanf("%d%d",&a,&b);
		check(a,b);
	}
	printf("%d\n%lld\n",satisfac,ans);
}
int main(){
	freopen("vacationgold.in","r",stdin);
	freopen("vacationgold.out","w",stdout);
	read();
	floyd();
	//for(int i=1;i<=K;i++){for(int j=1;j<=K;j++){cout<<hubdist[i][j]<<" ";}cout<<endl;}
	//for(int i=1;i<=N;i++){for(int j=0;j<c[i].size();j++){cout<<i<<" "<<c[i][j].first<<" "<<c[i][j].second<<endl;}}
	//for(int i=1;i<=N;i++){for(int j=0;j<ct[i].size();j++){cout<<i<<" "<<ct[i][j].first<<" "<<ct[i][j].second<<endl;}}
	//for(int i=1;i<=N;i++){for(int j=0;j<hc[i].size();j++){cout<<i<<" "<<hc[i][j].first<<" "<<hc[i][j].second<<endl;}}
	//for(int i=1;i<=N;i++){for(int j=0;j<hct[i].size();j++){cout<<i<<" "<<hct[i][j].first<<" "<<hct[i][j].second<<endl;}}
	//cout<<K<<" "<<hublis[1]<<" "<<hubid[1]<<endl;
	work();
	return 0;
}