HDU 6166 Senior Pan(2017 Multi-University Training Contest - Team 9)

HDU 6166 Senior Pan

题目大意:$n$ 个点$m$ 条边的有向图中,给定$k$ 个点,问这$k$ 个点两两间的最短路的最小值。

Dijkstra

因为题目要求的是两两不同点间的最短路,故可以将这k个点划分成两个集合,一个连接虚起点,另一个连接虚终点,求起点到终点的最短路即可。

如何划分?看到群里有人是用随机化划分过的,除了随机化还有一种靠谱的放法。

枚举二进制的每一位,将这$k$ 个数分成两个集合,这种做法保证了每两个点至少被分到两个集合一次。

复杂度$O(nlog^2n)$ 。

代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
struct edge{
    int t,w;
    edge(int T,int W){t=T;w=W;}
};
struct node{
    int v,d;
    node(int V,int D){v=V;d=D;}
    friend bool operator<(node a,node b){
        return a.d>b.d;
    }
};
const int N=100005;
const int inf=1e9;
vector<edge>e[N];
int vis[N],dis[N],adj[N][3];
priority_queue<node>q;
int dijkstra(int s,int t){
    while(!q.empty())q.pop();
    memset(vis,0,sizeof(vis));
    for(int i=s;i<=t;++i)dis[i]=inf;
    dis[s]=0;
    q.push(node(s,0));
    while(!q.empty()){
        node t=q.top();q.pop();
        int u=t.v;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<(int)e[u].size();++i){
            int v=e[u][i].t,w=e[u][i].w;
            dis[v]=min(dis[u]+w,dis[v]);
            if(!vis[v])q.push(node(v,dis[v]));
        }
    }
    return dis[t];
}
int T,n,m,k,a[N];
int main(void){
    scanf("%d",&T);
    for(int t=1;t<=T;++t){
        int ans=inf;
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;++i)
            for(int j=0;j<3;++j)
                scanf("%d",&adj[i][j]);
        scanf("%d",&k);
        for(int i=0;i<k;++i)
            scanf("%d",&a[i]);
        for(int i=0;i<20;++i){
            for(int op=0;op<2;++op){
                for(int j=0;j<=n+1;++j)e[j].clear();
                for(int j=0;j<m;++j)e[adj[j][0]].push_back(edge(adj[j][1],adj[j][2]));
                for(int j=0;j<k;++j){
                    if(((a[j]>>i)&1)==op)e[0].push_back(edge(a[j],0));
                    else e[a[j]].push_back(edge(n+1,0));
                }
                ans=min(ans,dijkstra(0,n+1));
            }
        }
        printf("Case #%d: %d\n",t,ans);
    }
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×