比赛 |
20140307 |
评测结果 |
AWWWWWWWWW |
题目名称 |
假期旅行计划 |
最终得分 |
10 |
用户昵称 |
digital-T |
运行时间 |
2.490 s |
代码语言 |
C++ |
内存使用 |
62.28 MiB |
提交时间 |
2014-03-07 20:33:10 |
显示代码纯文本
#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;
for(int i=1;i<=Q;i++)
{
scanf("%d%d",&a,&b);
for(int j=1;j<=K;j++)
{
if(ver[a][j]!=INF&&dis[j][b]!=INF)//using bottom[i]
{
ans++;
Ans+=(ver[a][j]+dis[j][b]);
break;
}
}
//printf("%d\n%lld\n",ans,Ans);
}
printf("%d\n%lld\n",ans,Ans);
return 0;
}