欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 5521 Meeting ( nlogn的dijkstra+拆点)

程序员文章站 2022-06-02 23:31:13
...
  • 题目链接: HDU 5521

  • 题意:

    给定n和m,n表示n个点,m表示m个集合,给出每个集合包含的点的编号,第i个集合中各个点之间的距离为ti,问,A位于编号为1的点,B位于编号为n的点,若同时出发,最快需要多久能相遇(可停留在某点等待), 输出最小时间以及满足最小时间的相遇的点.

  • 解法:

    这道题目,很裸的dijkstra最短路,但是依据题目,若集合中两两建边,则边数可达到1e12,爆空间 ,所以采用拆点形式,给每个集合额外分配一个点,集合中所有的点直接与这个点相连,距离为ti, 则最终答案需要除以2.

  • 图解:
  • 未拆点前,集合中点的连接,(每条边都是双向)
    HDU 5521 Meeting ( nlogn的dijkstra+拆点)
    • 1到2的距离 = 2到3的距离 = 3到1的距离 = ti
    • 每个集合都得建立s^2条边, s表示集合的大小
  • 拆点后
    HDU 5521 Meeting ( nlogn的dijkstra+拆点)

    • 1到2的距离 = 2到3的距离 = 3到1的距离 = 2 * ti
    • 每个集合都得建立2*s条边, s表示集合的大小
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i<=b; ++i)
#define repp(i,a,b) for(int i=b; i>=a; --i)
#define mp make_pair
#define pb push_back
#define ms(a, b) memset(a, b, sizeof(a))
#define inf 0x3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int>vi;

const int maxn = 2e6+7;
struct edge{
    int to,next;
    ll w;
}e[maxn];
int fi[maxn], id=0;
void adde(int u, int v, int w){
    //cout <<" pair => " << u<<" "<<v<<endl;
    e[id].to = v;
    e[id].w=w;
    e[id].next = fi[u];
    fi[u] = id++;
    return ;
}

ll dis[2][maxn];
ll status;
struct cmp{
    bool operator()( const int &a, const int &b){
        return dis[status][a] > dis[status][b];
    }
};
bool in[maxn];
void dij(int u, int s){
    ms(in, false);
    status = s;
    priority_queue<int, vector<int>, cmp>que;
    int i;
    dis[status][u] = 0;
    in[u] = 1;
    que.push(u);
    while(!que.empty()){
        int v = que.top();
        //cout << v <<endl;
        in[v]=1;
        que.pop();
        for(i=fi[v]; ~i; i=e[i].next){
            int to = e[i].to;
            if(in[to]) continue;
            if(dis[status][to] > dis[status][v]+e[i].w){
                dis[status][to] = dis[status][v]+e[i].w;
                que.push(to);
            }
        }
    }
    return ;
}
void init(){
    ms(dis, inf), ms(fi,  -1);
    id = 0;
    return ;
}
int ans[100005];
int main(){
//  freopen("in.txt", "r", stdin);

    int t, n, m, cas=0;
    scanf("%d", &t);
    while(t--){
        init();
        //cout << dis[0][0]<<endl;
        ll w;
        int  len, v;
        scanf("%d %d", &n, &m);
        rep(i, 1, m){
            scanf("%lld %d", &w, &len);
            rep(j, 1, len){
                scanf("%d", &v);
                adde(i, v+m, w);
                adde(v+m, i, w);
            }
        }
        dij(1+m, 0);
        ll d = inf;
        int alen=0;
        if(dis[0][n+m] != inf){
            dij(n+m, 1);
            rep(i, 1, n){
                ll tmp = max(dis[0][i+m], dis[1][i+m]);
                if(tmp < d){
                    d = tmp;
                    alen = 0;
                    ans[alen++]=i;
                } else if(tmp == d){
                    ans[alen++]=i;
                }
            } 

        }

        printf("Case #%d: ", ++cas);

        if(d!=inf) {
            printf("%d\n", d/2);    
            rep(i, 0, alen-2){
                printf("%d ", ans[i]);
            }
            printf("%d\n", ans[alen-1]);
        } else {
            printf("Evil John\n");
        }
    }
    return 0;
}
相关标签: dijkstra hdu