比赛 20140307 评测结果 WWWWWWWWWW
题目名称 假期旅行计划 最终得分 0
用户昵称 雪狼 运行时间 3.808 s
代码语言 C++ 内存使用 140.84 MiB
提交时间 2014-03-07 19:44:57
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define REP(i,a,b) for(int i=a;i!=b+1;++i)
#define CLR(c,x) memset(c,x,sizeof(c))
#define INF ~0U>>2
#define maxn 20000+10
#define maxk 500+10
#define eps 1e-9
using namespace std;
typedef long long LL;

vector<pair<int,int> >g[2][maxn];
int n,m,k,q;
int hubs[maxk],cnt;
LL dis[2][maxk][maxn],sum;

void spath(int h,int t){
	bool mark[n];
	//REP(i,0,n)mark[i]=0,dis[t][h][i]=INF;
	fill(mark,mark+n,false);
	fill(dis[t][h],dis[t][h]+n,INF);
	
	dis[t][h][hubs[h]]=0;
	priority_queue<pair<LL,int> >Q;
	Q.push(make_pair(0,hubs[h]));
	
	while(!Q.empty()){
		int x=Q.top().second;Q.pop();
		if(mark[x])continue;
		mark[x]=1;
		REP(i,0,g[t][x].size()-1){
			int v=g[t][x][i].first,d=g[t][x][i].second;
			if(dis[t][h][v]>dis[t][h][x]+d){
				dis[t][h][v]=dis[t][h][x]+d;
				Q.push(make_pair(-(dis[t][h][x]+d),v));
			}
		}
	}
}

void setIO(string s){
	string in=s+".in",out=s+".out";
	freopen(in.c_str(),"r",stdin);
	freopen(out.c_str(),"w",stdout);
}

int main(){
	setIO("vacationgold");
	
	scanf("%d%d%d%d",&n,&m,&k,&q);
	int a,b,c;
	REP(i,0,m-1){
		scanf("%d%d%d",&a,&b,&c);
		g[0][a-1].push_back(make_pair(b-1,c));
		g[1][b-1].push_back(make_pair(a-1,c));
	}
	
	REP(i,0,k-1){
		scanf("%d",hubs+i);
		--hubs[i];
		spath(i,0);
		spath(i,1);
	}
	
	REP(i,0,q-1){
		scanf("%d%d",&a,&b);
		LL cost=INF;
		REP(j,0,k-1)
			cost=min(cost,dis[1][j][a-1]+dis[0][j][b-1]);
		if(cost!=INF)cnt++,sum+=cost;
	}
	
	printf("%lld\n%lld\n",cnt,sum);
	return 0;
}