[USACO13DEC] Vacation Planning G

题目传送门

[USACO13DEC] Vacation Planning G

思路

总结：一点点小思维+最短路板子。

显然我们发现，对于每一次询问的出发点 \(u\) 只有两种可能：是中枢或者不是中枢。

同时注意到，\(K\) 的范围非常小，所以可以考虑在中枢上做文章。我们可以先试着在 \(K\) 个中枢中跑 \(K\) 遍最短路。然后分类讨论（假定中枢点集合为 \(S\)）：

• \(u\in S\)：显然我们已经处理过了 \(u\) 的最短路，所以我们可以直接判断 \(u\) 是否可以到 \(v\) 并且很快查询其花费。

• \(u\notin S\)：根据题目性质可以得出每一个与 \(u\) 相连的节点 \(w\) 都满足 \(w\in S\)，而每一个 \(w\) 的最短路也已知，所以可以遍历一遍 \(u\) 所能到达的点再查询花费。

注意到每一个中枢的范围在 \([1,N]\)，似乎二维的最短路数组存不下，那就先给它离散化一下吧，这样每一个中枢的范围就控制在了 \([1,K]\)。

似乎 SPFA 都可以跑过去，但我们还是选择 Dijkstra。

最坏时间复杂度为 \(O(KN\log(N+M)+KQ)\)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){
    int x=0,f=1;
    char c=getchar();

    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') f=-1;

    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';

    return x*f;
}

inline void Write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }

    if(x>9) Write(x/10);

    putchar(x%10+'0');
}

inline void write(int x){
    Write(x);
    putchar('\n');
}

const int MAXN=20005,MAXK=205;
int n,m,k,q;
vector<pair<int,int> >V[MAXN];
int hub[MAXK],id[MAXN]={0},cnt=0;
int dis[MAXK][MAXN],tot=0,ans=0;
bool vis[MAXN]={0},ishub[MAXN]={0};

void dijkstra(int s){
	for(int i=1;i<=n;i++)
		vis[i]=0;
	
	priority_queue<pair<int,int> >q;
	dis[id[s]][s]=0;
	q.push(make_pair(0,s));
	
	while(!q.empty()){
		int t=q.top().second;
		q.pop();
		
		if(vis[t]) continue;
		else vis[t]=1;
		
		for(int i=0;i<V[t].size();i++){
			int to=V[t][i].first;
			int w=V[t][i].second;
			
			if(dis[id[s]][to]>dis[id[s]][t]+w){
				dis[id[s]][to]=dis[id[s]][t]+w;
				q.push(make_pair(-dis[id[s]][to],to));
			}
		}
	}
}

signed main(){
	n=read(),m=read();
	k=read(),q=read();
	
	for(int i=1;i<=k;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=1e17;
	
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		V[u].push_back(make_pair(v,w));
	}
	
	for(int i=1;i<=k;i++){
		hub[i]=read();
		ishub[hub[i]]=1;
		id[hub[i]]=(++cnt);
	}
	
	for(int i=1;i<=k;i++)
		dijkstra(hub[i]);
		
	while(q--){
		int u=read(),v=read();
		
		if(ishub[u]){
			if(dis[id[u]][v]!=1e17){
				tot++;
				ans+=dis[id[u]][v];
			}
		}
		else{
			int mn=1e17;
			
			for(int i=0;i<V[u].size();i++){
				int to=V[u][i].first;
				int w=V[u][i].second;
				mn=min(dis[id[to]][v]+w,mn);
			}
			
			if(mn!=1e17){
				tot++;
				ans+=mn;
			}
		}
	}
	
	write(tot);
	write(ans);

    return 0;
}