比赛 |
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;
}