草庐IT

AcWing1134/洛谷P1144 最短路计数

StkOvflow 2023-03-28 原文

AcWing传送门
洛谷传送门

题目大意

\(\qquad\)给一个无向图，边权都是\(1\)，求出以\(1\)为源点，到各个点(\(1\sim n\))的最短路数量

解题思路

\(\qquad\)边权都是\(1\)的图中最短路，我们选择用\(BFS\)解决这个问题
\(\qquad\)对于每个点\(j\)，我们进行以下讨论：（假设这个\(j\)在这轮\(BFS\)中由\(i\)点转移而来)
\(\qquad\)\(1.\)当\(dist_{\ j} < dist_{\ i} + 1\)的时候，由于队列的性质，\(点1\)到\(点j\)的若干条最短路中\(\color{Red}{\huge 必定没有i}\)，所以我们可以直接忽视这种情况
\(\qquad\)\(2.\)当\(dist_{\ j} \ge dist_{\ i} + 1\)的时候，我们继续分成两类

\(\qquad \qquad \color{#0000ff}{\large a.}\ \ \ \large dist_{\ j} = dist_{\ i} + 1\)
\(\qquad\)\(\qquad\)在这种情况下，代表着\(i\)可以是\(1\sim j\)的最短路中的一个点，但是还有其它点，这里根据 加法原理 就可以得出我们\(cnt_{\ j}\)应该加上\(cnt_{\ i}\)（因为从\(1\sim i\)的任意一条最短路，再加上\(i\sim j\)这条边，都属于\(1\sim j\)的最短路）。
\(\qquad \qquad \color{#0000ff}{\large b.}\ \ \ \large dist_{\ j} = dist_{\ i} + 1\)
\(\qquad\)\(\qquad\)在这种情况下，代表\(i\)是目前第一个可以更新\(j\)的点，所以\(j\)是第一次被更新，需要入队，其它的操作和分类\(\color{#0000ff}{\large a}\)都是一样的

代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = N << 2, mod = 1e5 + 3;
int dist[N], n, m, cnt[N];
int h[N], e[M], ne[M], idx;

void add(int a, int b) 
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs() 
{
    memset(dist, 0x3f, sizeof dist);
    queue <int> q;
    
    dist[1] = 0, cnt[1] = 1, q.push(1);
    
    while (q.size()) 
    {
        auto t = q.front(); q.pop();
        
        for (int i = h[t]; ~i; i = ne[i]) 
        {
            int j = e[i];
            if (dist[j] > dist[t] + 1)
            {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t];
                q.push(j);
            }
            else if (dist[j] == dist[t] + 1) 
                cnt[j] = (cnt[j] + cnt[t]) % mod;
        }
    }
}

int main() 
{
    scanf("%d%d", &n, &m);
    
    memset(h, -1, sizeof h);
    while (m -- ) 
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    
    bfs();
    
    for (int i = 1; i <= n; i ++ ) 
        printf("%d\n", cnt[i]);
    
    return 0;
}
AcWingP1144spaninlineclass算法与数据结构

有关AcWing1134/洛谷P1144 最短路计数的更多相关文章

  1. ruby-on-rails - Ruby on Rails 计数器缓存错误 - 2

    尝试在我的RoR应用程序中实现计数器缓存列时出现错误Unknownkey(s):counter_cache。我在这个问题中实现了模型关联:Modelassociationquestion这是我的迁移:classAddVideoVotesCountToVideos0Video.reset_column_informationVideo.find(:all).eachdo|p|p.update_attributes:videos_votes_count,p.video_votes.lengthendenddefself.downremove_column:videos,:video_vot

  2. ruby - 使用多个数组创建计数 - 2

    我正在尝试按0-9和a-z的顺序创建数字和字母列表。我有一组值value_array=['0','1','2','3','4','5','6','7','8','9','a','b'，'光盘'，'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','','u','v','w','x','y','z']和一个组合列表的数组，按顺序，这些数字可以产生x个字符，比方说三个list_array=[]和一个当前字母和数字组合的数组(在将它插入列表数组之前我会把它变成一个字符串，]current_combo['0','0','0']

  3. Ruby 计数数组对象，如果对象包含值 - 2

    我有一个数组:array=['Footballs','Baseball','football','Soccer']而且我需要计算看到Football或Baseball的次数，无论大小写和复数形式如何。这是我尝试做的，但没有成功:array.count{|x|x.downcase.include?'football'||x.downcase.include?'baseball'}编写这段代码的正确或更好的方法是什么？我正在寻找3作为答案。 最佳答案 我会将count与一个block结合使用，该block根据与您正在寻找的约束相匹配的正

  4. ruby - AWS 上远程机器上的进程计数 - 2

    我正在为在AmazonEC2实例上运行的应用程序设计一个AutoScaling系统。应用程序从SQS读取消息并对其进行处理。AutoScaling系统将监控两件事:SQS中的消息数量，所有EC2机器上运行的进程总数。例如，如果SQS中的消息数量超过3000，我希望系统自动缩放，创建一个新的EC2实例，在其上部署代码，当消息数量低于2000时，我希望系统终止EC2实例.我正在用Ruby和Capistrano做这件事。我的问题是:我无法找到一种方法来确定在所有EC2机器上运行的进程数并将该数字保存在变量中。你能帮帮我吗？ 最佳答案 您可

  5. ruby-on-rails - FactoryGirl工厂特征内的序列不使用主序列计数器 - 2

    我有以下工厂:FactoryGirl.definedofactory:foodosequence(:name){|n|"Foo#{n}"}trait:ydosequence(:name){|n|"Fooy#{n}"}endendend如果我跑create:foocreate:foocreate:foo,:y我得到Foo1,Foo2,Fooy1。但我想要Foo1,Foo2,Fooy3。我怎样才能做到这一点？ 最佳答案 经过smile2day'sanswer的一些提示后和thisanswer，我得出以下解决方案:FactoryGirl.

  6. ruby - 续集:如何使用分组和计数 - 2

    简单地说，我如何使用Sequel执行此查询？selecta.id,count(t.id)fromalbumsarightjointrackstont.album_id=a.idgroupbya.id 最佳答案 DB[:albums___a].right_join(:tracks___t,:album_id=>:id).select_group(:a__id).select_more{count(:t__id)} 关于ruby-续集:如何使用分组和计数，我们在StackOverflow上找

  7. ruby-on-rails - RSpec 检查数组的计数 - 2

    我正在测试我的ControllerAction以供练习。在我的Controller中，我只想从我的数据库中按名称获取所有不同的产品:defshop@products=Product.select('distincton(name)*').sort_by&:orderend我已经手动检查过了，它工作正常。现在我正在使用我的RSpec设置我的测试，我想测试@products是一个大于0的数组:RSpec.describePagesController,type::controllerdodescribe'GET#shop'doit'shouldgetallproudcts'doget:sh

  8. arrays - ruby 中的最佳排列计数算法 - 2

    我正在尝试计算由二进制形式的1和0的P数表示的数字的数量。如果P=2，则表示的数字为0011、1100、0110、0101、1001、1010，所以计数为6。我试过:[0,0,1,1].permutation.to_a.uniq但这不是大数的最佳解决方案(P可以什么可能是最好的排列技术，或者我们是否有任何直接的数学来做到这一点？ 最佳答案 Numberofpermutationcanbecalculatedusingfactorial.a=[0,0,1,1](1..a.size).inject(:*)#=>4!=>24要计算重复项，

  9. Ruby 惯用法短路返回第一个非零使用每个和映射 - 2

    这是我正在尝试做的事情的本质，但“中断”不正确:needle=nilhaystacks.eachdo|haystack|needle=haystack.look_for_needle()breakifneedleend这更短，但它会遍历每个干草堆(至少不看)，即使它不需要:needle=nilhaystacks.eachdo|haystack|needle||=haystack.look_for_needle()end这是一个单行代码，但(我相信)它并不懒惰，所以它做了不必要的工作:needle=hackstacks.map{|h|h.look_for_needle()}.detect

  10. ruby-on-rails - Rails 计数器缓存及其实现 - 2

    我正在尝试掌握Rails计数器缓存功能，但无法完全掌握它。假设我们有3个模型ABCA属于B或C，取决于字段key_type和key_id。key_type表示A属于B还是C，因此如果key_type="B"则记录属于B，否则属于C。在我的模型a.rb中，我定义了以下关联:belongs_to:b,:counter_cache=>true,:foreign_key=>"key_id"belongs_to:c,:counter_cache=>true,:foreign_key=>"key_id"和在b和c模型文件中has_many:as,:conditions=>{:key_type=>"

随机推荐