计算两个给定节点之间的最短可能路由

Question

我最近遇到了这问题：

印度电影中的英雄有着超人的功绩。例如，他们可以跳在建筑物之间，跳上或从运行中的火车，用他们的手和牙齿捕捉子弹等等。一位敏锐的影迷会发现，即使是超级英雄，也是有限度的。例如，如果英雄可以直接跳到他的最终目的地，这将减少动作序列为零，从而使电影相当无聊。因此，他通常通过一系列超人的步骤来达到他的最终目的。在这个问题上，我们的英雄必须拯救他的妻子/母亲/孩子/狗/.被可怕的恶棍俘虏在孟买/曼谷/吉隆坡/.中心的一座高楼的顶层。我们的英雄在一座(不同的)建筑物的顶上。为了使这个动作“有趣”，导演决定英雄只能在彼此“接近”的建筑之间跳跃。主任决定哪对建筑物足够近，哪些不是。给出建筑物清单，英雄开始搜寻的建筑物的身份，被俘者(妻子/母亲/孩子/狗)的身份。举行，和一套对的建筑物，英雄可以跳过，你的目标是决定是否有可能为英雄到达俘虏。而且，如果他能到达俘虏，他想这样做，以最低数量的跳跃。下面是一个例子。有5栋建筑，编号为1,2，...,5，英雄站在1号楼上，被俘者站在4号楼上。导演认为，建筑物1和3、2和3、1和2、3和5以及4和5非常接近，足以让英雄跳过。英雄可以从1跳到3，然后从3跳到5，最后从5跳到4。(注意，如果我和j很近，那么英雄可以从i跳到j，也可以从j跳到i。)在这个例子中，英雄也可以从1跳到2、2到3、3到5，最后从5跳到4。第一条路线使用3次跳跃，第二条路线使用4次跳跃。您可以验证3跳是最好的可能。如果导演决定，只有一对建筑物足够近，1和3，1和2和4和5，那么英雄将无法到达4号楼，以拯救被俘者。

这是广度优先的搜索问题，很容易解决。

#include <iostream>
#include <vector>
#include <queue>

int main (int argc, char const* argv[])
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int> >table(n,std::vector<int>(n));
    while(m--){
        int a ,b;
        std::cin >> a >> b;
        table[a-1][b-1] = 1;
        table[b-1][a-1] = 1;
    }
    int start , end;
    std::cin >> start >> end;
    start--;end--;
    std::vector<bool>visited(n);
    std::queue<int>queue_;
    visited[start] = true;
    queue_.push(start);
    std::vector<int>minDist(n);
    std::fill(minDist.begin(),minDist.end(),31000);
    minDist[start] = 0;
    while(!queue_.empty()){
        int s = queue_.front();
        queue_.pop();
        for(int i=0;i<n;i++){
            if(!visited[i] && table[s][i] == 1){
                visited[i] = true;
                minDist[i] = std::min(minDist[i],minDist[s]+1);
                queue_.push(i);
            }
        }
    }
    std::cout <<minDist[end]<< std::endl;
    return 0;
}

代码通过了10个测试用例中的9个，并被困在了第10个测试用例中，这真是太大了。它甚至没有在我自己的机器上运行。

下面是5 MBs：存档中的第十个测试用例的测试用例

有人能给我一些技巧，为这么大的输入优化代码吗？

Answer 1

输入文件中断

您链接的第十个测试用例失败了，因为第一行是这样的：

3500 641902

但是只有641901条边，而不是641902条。最后一行是开始/结束对。因此，当您在这个输入文件上运行您的程序时，您将读取最后一行(开始/结束对)，就好像它是一个边缘。然后，尝试在开始/结束对中阅读，并得到垃圾。我把641902改为641901来修正这个文件。在此之后，您的程序运行良好，但遇到了一个小错误(请参阅下一节)。

Bug

该问题指定，如果没有路径，程序应该打印0。您可以编程打印31000，例如在固定的10.in输入文件上。您应该修改您的程序以检测无路径情况。换句话说，如果最小距离结束为31000 (即“最大”距离)，则打印0。

用于解析输入

的所有时间

您的程序花了4.27秒来解决最困难的测试案例。但是我发现4.27秒中的4.21秒仅仅用于做cin >> a >> b。我在这个堆叠溢出问题上读到，解决这个问题的方法是这样做：

std::ios_base::sync_with_stdio(false);

在我添加了上面的代码之后，对于最困难的测试用例，它将程序的运行时间从4.27秒缩短到0.14秒。

这被接受了

我刚刚提交了这个计划，并且被接受了。这是您的程序，其中有我提到的两个修复程序：

1. 如果没有路径，则打印0。
2. 检查错误输入，如果输入文件被破坏，则打印0。

以下是节目：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

int main (int argc, char const* argv[])
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int> >table(n,std::vector<int>(n));
    while(m--){
        int a ,b;
        std::cin >> a >> b;
        table[a-1][b-1] = 1;
        table[b-1][a-1] = 1;
    }
    int start , end;
    std::cin >> start >> end;
    start--;end--;
    if (start < 0 || start >= n || end < 0 || end >= n) {
        std::cout << "0" << std::endl;
        return 0;
    }

    std::vector<bool>visited(n);
    std::queue<int>queue_;
    visited[start] = true;
    queue_.push(start);
    std::vector<int>minDist(n);
    std::fill(minDist.begin(),minDist.end(),INT_MAX);
    minDist[start] = 0;
    while(!queue_.empty()){
        int s = queue_.front();
        queue_.pop();
        for(int i=0;i<n;i++){
            if(!visited[i] && table[s][i] == 1){
                visited[i] = true;
                minDist[i] = std::min(minDist[i],minDist[s]+1);
                queue_.push(i);
            }
        }
    }
    if (minDist[end] == INT_MAX)
        std::cout << "0" << std::endl;
    else
        std::cout <<minDist[end]<< std::endl;
    return 0;
}