[USACO 2013 Gold] Vacation Planning

作法：

記題目給定的那 k 個點為黑點。首先預處理出每個黑點到其他 n 個點的最短路長，那麼當在求 x ~ y 的最短路時，如果 x 本身就是黑點，那就直接查表即可。而如果不是的話，考慮所有從 x 連出去的邊，由題目給的條件可知連到的點都是黑點，而黑點個數又不會超過 k 個，所以我們可以直接枚舉 x 要走到哪個黑點，再去查那個黑點走到 y 的最短距離，對所有的可能取 min 即可。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF 1000000000
using namespace std;
const int maxn=20000+10,maxk=200+10 ;
 
struct P{int to,dis;};
struct Q
{
    int id,val ;
    bool operator < (const Q &rhs) const
    {
        return val>rhs.val ;
    }
};
 
priority_queue<Q> pq ;
vector<P> v[maxn] ;
int n ;
bool done[maxn] ;
 
void Dijkstra(int st,int *d)
{
    while(!pq.empty()) pq.pop() ;
    memset(done,0,sizeof(done)) ;
    fill(d+1,d+n+1,INF) ; d[st]=0 ;
    pq.push((Q){st,0}) ;
    while(!pq.empty())
    {
        Q u=pq.top() ; pq.pop() ;
        if(done[u.id]) continue ;
        done[u.id]=1 ;
        for(auto i : v[u.id]) if(d[i.to] > d[u.id]+i.dis)
            d[i.to]=d[u.id]+i.dis , pq.push((Q){i.to,d[i.to]}) ;
    }
}
 
int d[maxk][maxn] ;
vector<int> K ;
bool hub[maxn] ;
 
main()
{
    freopen("vacationgold.in","r",stdin) ;
    freopen("vacationgold.out","w",stdout) ;
    int m,k,Q ; scanf("%d%d%d%d",&n,&m,&k,&Q) ;
    while(m--)
    {
        int x,y,dis ; scanf("%d%d%d",&x,&y,&dis) ;
        v[x].push_back((P){y,dis}) ;
    }
    while(k--)
    {
        int x ; scanf("%d",&x) ;
        hub[x]=1 ; K.push_back(x) ;
    }
    sort(K.begin(),K.end()) ;
 
    for(int i=0;i<K.size();i++) Dijkstra(K[i],d[i]) ;
 
    LL ans1=0LL , ans2=0LL ;
    while(Q--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        if(hub[x])
        {
            int id=lower_bound(K.begin(),K.end(),x)-K.begin() ;
            if(d[id][y]!=INF) ans1++ , ans2+=d[id][y] ;
        }
        else
        {
            int ans=INF ;
            for(auto i : v[x])
            {
                int id=lower_bound(K.begin(),K.end(),i.to)-K.begin() ;
                ans=min(ans,i.dis+d[id][y]) ;
            }
            if(ans!=INF) ans1++ , ans2+=ans ;
        }
    }
    printf("%lld\n%lld\n",ans1,ans2) ;
}