比赛 |
20140307 |
评测结果 |
AETEEEEEEE |
题目名称 |
假期旅行计划 |
最终得分 |
10 |
用户昵称 |
超级傲娇的AC酱 |
运行时间 |
2.907 s |
代码语言 |
C++ |
内存使用 |
0.31 MiB |
提交时间 |
2014-03-07 20:39:47 |
显示代码纯文本
/*
King_CH_Designed
on 2014/3/7
*/
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int oo=~0u>>1;
vector<vector<int> >A;
vector<vector<pair<pair<int,int>,bool> > >E;
int Djs(int,int);
int n,m,k,q;
int main()
{
int i,j,p,x,y,num=0,Ans=0;
freopen("vacationgold.in","r",stdin);
freopen("vacationgold.out","w",stdout);
ios::sync_with_stdio(false);
cin>>n>>m>>k>>q;
A.resize(n);E.resize(n);
for(i=0;i<n;i++)
{
A[i].resize(n);
for(j=0;j<n;j++)A[i][j]=oo;
A[i][i]=0;
}
for(i=0;i<m;i++)
{
cin>>x>>y>>p;
E[x-1].push_back(make_pair(make_pair(p,y-1),false));
}
for(i=0;i<k;i++)
{
cin>>x;
for(j=0;j<E[x-1].size();j++)
E[i][j].second=true;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i!=j)A[i][j]=Djs(i,j);
for(i=0;i<q;i++)
{
cin>>x>>y;
if(A[x-1][y-1]!=oo)
{
num++;
Ans+=A[x-1][y-1];
}
}
cout<<num<<endl<<Ans;
return 0;
}
int Djs(int s,int e)
{
priority_queue<pair<int,pair<int,bool> >,vector<pair<int,pair<int,bool> > >,greater<pair<int,pair<int,bool> > > >Q;
Q.push(make_pair(0,make_pair(s,false)));
vector<bool>v(n,false);
int pos,Len,i;
bool Sg;
while(!Q.empty())
{
Len=Q.top().first;
pos=Q.top().second.first;
Sg=Q.top().second.second;
Q.pop();
if(pos==e)
{
if(Sg==false)
goto CH;
else
return Len;
}
if(v[pos]==false)
{
v[pos]=true;
for(i=0;i<E[pos].size();i++)
if(v[E[pos][i].first.second]==false)
{
//v[E[pos][i].first.second]=true;
Q.push(make_pair(Len+E[pos][i].first.first,make_pair(E[pos][i].first.second,Sg|E[pos][i].second)));
}
}
CH:;
}
return oo;
}