首页 > 其他分享 >Loj P10064 黑暗城堡 题解 最短路径树记数

Loj P10064 黑暗城堡 题解 最短路径树记数

时间:2024-07-21 18:27:33浏览次数:16  
标签:emplace cur Loj 题解 ll 路径 second P10064 dis

这道题是一道最短路径树问题。

首先,什么是最短路径树呢?

定义一个图的最短路径树表示一个图上的生成树,且根节点到图上任一点的距离等于原图上两者之间的距离。

而不难发现,题目其实是在求图上最短路径树记数。

首先,建出最短路径树。枚举每条边,判断边两个端点到根的距离之差是否为这条边的边权。如果是,则在最短路径树中加入这条边。

然后,通过乘法原理可知,最短路径树记数其实就是求出每个最短路径树上的点的入度的积。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
const ll N = 1010, mod = 0x7fffffff;
ll n, m;
ll ans = 1;
vector<p> graph[N], graph2[N], graph3[N];
vector<ll> dis(N, 1e9);
bitset<N> vis;
void dijkstra() {
    priority_queue<p, vector<p>, greater<>> q;
    q.emplace(0, 1);
    dis[1] = 0;
    while (!q.empty()) {
        p cur = q.top();
        q.pop();
        if (vis[cur.second])
            continue;
        vis[cur.second] = 1;
        for (auto v : graph[cur.second]) {
            if (dis[v.second] > dis[cur.second] + v.first) {
                dis[v.second] = dis[cur.second] + v.first;
                q.emplace(dis[v.second], v.second);
            }
        }
    }
    for (ll i = 1; i <= n; i++) {
        for (auto v : graph[i]) {
            if (dis[i] == dis[v.second] + v.first) {
                graph2[v.second].emplace_back(v.first, i);
                graph3[i].emplace_back(v.first, v.second);
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (ll i = 0, u, v, w; i < m; i++) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }
    dijkstra();
    vis.reset();
    for (int i = 1; i <= n; i++)
        if (!graph3[i].empty()) {
            ans = (ans * graph3[i].size()) % mod;
        }
    cout << ans;
    return 0;
}

 

标签:emplace,cur,Loj,题解,ll,路径,second,P10064,dis
From: https://blog.csdn.net/iPig4/article/details/140591543

相关文章

  • 【题解】P4648 [IOI2007] pairs 动物对数
    Problem给定模板\(B(1\leB\le3)\),代表\(B\)维空间。其中有\(n\)个点,给出坐标与坐标上限\(M\),求\(n\)个点中曼哈顿距离\(\leD\)的对数。Solve\(B=1\)考虑将问题化简成:求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^{i-1}[dis(i,j)\leqD]\)。其中\(dis(i,j)\)......
  • 圆方树学习笔记 & 最短路 题解
    前言圆方树学习笔记,从一道例题讲起。题目链接:Hydro&bzoj。题意简述仙人掌上求两点距离。题目分析为了把仙人掌的性质发挥出来,考虑将其变成一棵树。圆方树就是这样转换的工具。先讲讲圆方树的概念:原图上的点为圆点,每个点双对应一个方点,树边都是方点连向点双内的圆点。具......
  • 跑步爱天天 题解
    题意简述一棵以\(1\)为根的树,儿子间有先后顺序。初始每个结点上有一个警卫,警卫按照深度优先遍历其子树,儿子间的先后顺序体现在这里,回到起始点后开始新一轮的遍历。yzh想要从\(S\)走到\(1\),请问她会在路上遇到多少警卫(\(S\)点的也算)。题目分析法\(1\)先来讲一讲我考场......
  • 题解:Codeforces Round 960 (Div. 2) D
    D.GridPuzzletimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenanarray\(a\)ofsize\(n\).Thereisan\(n\timesn\)grid.Inthe\(i\)-throw,thefirst\(a_i\)......
  • 【2024最新华为OD-C/D卷试题汇总】[支持在线评测] LYA的生日派对座位安排(200分) - 三
    ......
  • 题解:Codeforces Round 960 (Div. 2) C
    C.MadMADSumtimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputWedefinethe\(\operatorname{MAD}\)(MaximumAppearingDuplicate)inanarrayasthelargestnumberthatappearsatleast......
  • NOI2024 集合 题解
    给个链接:集合。很神秘的题目。基本上看到之后就可以想到哈希。首先想到一个比较神秘的暴力。就是对于每个询问,扫一遍所有\(a\)中的数出现的位置,把它弄成一个哈希值(具体怎么弄随意)存到set里,然后看看是不是和\(b\)中的数出现的位置这样操作后的集合完全相等。事实上就是判断......
  • B3956 [GESP202403 三级] 字母求和 题解
    B3956[GESP202403三级]字母求和题解当时在考试,3分钟A了,结果第二题T了。#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+2;constintN1=1e3+2;typedeflonglongll;typedefunsignedlonglongull;#definefo(i,n,m)for(inti=n;i<=m;i++)......
  • 【科大讯飞笔试题汇总】2024-07-20-科大讯飞秋招提前批(研发岗)-三语言题解(Cpp/Java/
    ......
  • 题解:Codeforces Round 960 (Div. 2) B
    B.ArrayCrafttimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputForanarray\(b\)ofsize\(m\),wedefine:themaximumprefixpositionof\(b\)isthesmallestindex\(i\)thatsat......