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