首页 > 其他分享 >Codeforces2014E Rendez-vous de Marian et Robin(分层图最短路)

Codeforces2014E Rendez-vous de Marian et Robin(分层图最短路)

时间:2024-10-01 19:22:20浏览次数:7  
标签:Codeforces2014E vous dist Marian int vector ans emplace adj

题意

给定一个无向图,含有 \(n\) 个点和 \(m\) 条边。

题解

点击查看代码
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

constexpr i64 inf = 1e18;

void solve() {
    int n, m, h;
    cin >> n >> m >> h;

    vector<vector<pair<int, int>>> adj(2 * n);
    for (int i = 0; i < h; i++) {
        int a;
        cin >> a;
        a--;
        
        adj[a].emplace_back(a + n, 0);
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;

        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
        adj[u + n].emplace_back(v + n, w / 2);
        adj[v + n].emplace_back(u + n, w / 2);
    }

    auto dijkstra = [&](int s) {
        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> Q;
        vector<i64> dist(2 * n, inf);
        vector<bool> vis(2 * n, false);

        dist[s] = 0LL;
        Q.emplace(0LL, s);
        while (!Q.empty()) {
            int u = Q.top().second;
            Q.pop();

            if (vis[u]) {
                continue;
            }
            vis[u] = true;
            for (auto [v, w] : adj[u]) {
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    Q.emplace(dist[v], v);
                }
            }
        }
        
        vector<i64> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = min(dist[i], dist[i + n]);
        }
        return ans;
    };

    vector<i64> D1 = dijkstra(0), D2 = dijkstra(n - 1);
    i64 ans = inf;
    for (int i = 0; i < n; i++) {
        ans = min(ans, max(D1[i], D2[i]));
    }

    if (ans == inf) {
        ans = -1;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        solve();
    }
    return 0;
}

标签:Codeforces2014E,vous,dist,Marian,int,vector,ans,emplace,adj
From: https://www.cnblogs.com/LDUyanhy/p/18443131

相关文章

  • Luogu P10010 Grievous Lady
    很水的一道黑传送门题目大意给出\(n\)个元素,每个元素有两个权值\(a_i\)和\(b_i\),从中选出若干元素,令取出元素的\(a_i\)之和为\(S_a\),其余元素的\(b_i\)之和为\(S_b\),最大化\(S_a*S_b\)分析可以知道\(a_i\),\(b_i\)的值分别在\([1,A]\),\([1,B]\)......
  • POI2012RAN-Rendezvous
    POI#Year2012#基环树#lca分类讨论如果\(a,b\)不联通,\(-1\)如果\(a,b\)在同一棵子树下,最优策略一定是\(lca(a,b)\)如果\(a,b\)不在同一棵子树下,最优策略是\(rt_a,rt_b\)中的一个//Author:xiaruizeconstintN=5e5+10;#defineendl'\n'inthead[N],t......
  • [POI2012] Rendezvous 题解
    众所周知,\(lyh\)是一名压行大师,也是一名\(juruo\),所以他将他繁琐的方法用\(102\)行表现了出来……明显原题为基环内向树森林。首先用并查集计算连通块,不在一个连通块里的答案就是\(-1\-1\)。发现实际上答案就是以环为根节点,求\(lca\)的结果,求完后可以分为两种情况:根......
  • G. Mischievous Shooter
    原题链接思路简述二维差分+矩阵旋转思路详述1.二维差分,对于每一个标签而言,有对一维的影响和二维的传递之分2.为什么要差分?对于每一个目标而言,它对以其为左上角顶点,k为边长的三角形内的点都有一个贡献,这种范围内的累加就考虑用前缀和(这里是二维差分)3.为什么要矩阵旋转?由于在......
  • G. Mischievous Shooter
    G.MischievousShooterOncethemischievousandwaywardshooternamedShelfoundhimselfonarectangularfieldofsize$n\timesm$,dividedintounitsquares.Eachcelleithercontainsatargetornot.Shelonlyhadaluckyshotgunwithhim,withwhich......
  • TIBCO.Rendezvous简单的发消息的过程
    C#代码实现发消息的过程.首先需要安装,添加引用,usingTIBCO.Rendezvous;然后其实就是简单4个步骤,即可把讯息发出去;开启环境->实例化NetTransport->生成需要发送的Message->transport.Send(msg);最后关闭环境;1//开启环境;2TIBCO.Rend......
  • [swin-trans]分布式训练的debug:ValueError: Error initializing torch.distributed us
    在用torch.distributed.init_process_group(backend='nccl',init_method='env://',world_size=world_size,rank=rank)时,出现1、ValueError:Errorinitializingtorch.distributedusingenv://rendezvous:environmentvariableMASTER_ADDRexpected,b......
  • P3533 [POI2012] RAN-Rendezvous 题解
    P3533[POI2012]RAN-Rendezvous题目大意:给定外向树森林,每次给定两个起始点,求两个点沿边移动最少步数相遇。\(n\)个点,\(n\)条边,并且每个点有唯一的出边,显然构成了多棵基环树,对于每个基环树分别处理:找出环上的点,因为要求支持求出任意两点距离,前缀和一下即可。对于询问,如果在两......
  • Rendezvous hashing算法介绍
    RendezvoushashingRendezvoushashing用于解决分布式系统中的分布式哈希问题,该问题包括三部分:Keys:数据或负载的唯一标识Values:消耗资源的数据或负载Servers:管理数据或负载的实体例如,在一个分布式系统中,key可能是一个文件名,value是文件数据,servers是连接网络的数据服务器,......
  • Pytorch rendezvous 分布式
    PyTorch中的rendezvous后端是一种服务,它帮助分布式训练作业中的进程相互发现并协商角色和等级。它还提供了一个屏障和一个一致的作业成员和状态视图。 rendezvous后端是作为torch.distributed.elastic.rendezvous.RendezvousHandler的子类实现的,它定义了创建、加入和销毁rendez......