POJ 3255 Roadblocks 最短路 Dijkstra算法的简单应用

小灰灰 2023-07-11 12:41 55阅读 0赞

题目如下：

# Roadblocks #

Time Limit: 2000MS Memory Limit: 65536K  
Total Submissions: 25495 Accepted: 8833

### Description ###

Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.

The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1…N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.

The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).

### Input ###

Line 1: Two space-separated integers: N and R  
Lines 2…R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)

### Output ###

Line 1: The length of the second shortest path between node 1 and node N  
Sample Input

4 4  
1 2 100  
2 4 200  
2 3 250  
3 4 100  
Sample Output

450

#### Hint ####

Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450)

#### Source ####

USACO 2006 November Gold

[题目链接][Link 1]

这道题，求的是次短路，只需从最短路的基础上，进行变形即可。  
![本题的提交结果][20200305182822178.png]  
注意，这里要用邻接表，不然后超内存。  
这里使用了优先级队列来维护Dijkstra算法中的最小结点，复杂度(R\*log(N))，很轻松的过了这道题，只用了0.2秒时间。

当然不用也可以，复杂度为（N^2)，我实现了一下，完全可以过这道题，就是好使多了三倍，用了0.6秒，但这道题给了两秒的时间限制，很充裕，两种方法都可以实现，第二种简单些，第一种稳些。  
![在这里插入图片描述][20200305183236910.png]

考虑到图可能比较稀疏，有时候用不加优化的算法的话，容易超时间限制，所以较为简单的实现就不给大家了（其实我忘了保存了，交了后就没了），其实较为复杂的是怎么想，怎么做好一些细节的处理，单论代码量，实际上还要少一些的。  
这里，给大家的是第一种实现，具体的说明都在注释中了，这里不多加介绍，只要对Dijkstra稍有了解，应该都看得懂的。

## AC代码及说明 ##

#include <iostream>
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <queue>
    
    using namespace std;
    
    const int max_N = 5000+2;
    const int max_D = 5000+2;
    const int max_R = 1e5+2;
    // 这里我们不设INF为0x7fffffff;
    // 因为在如此题最短路等一些图论的算法中，设这样大的值，会在松弛操作时，加和会导致数据溢出
    // 设为0x3f3f3f3f(注意这里是四个3f，手滑容易打成三个）
    // 0x3f3f3f3f的十进制是1061109567，也是10^9级别的（和0x7fffffff一个数量级），足够用了
    // 此题最大值不过是max_N * max_D
    // 一般算法竞赛中，常有将上限设成10^9数量级以下的，这是个很好的选择
    // 可以用memset快速初始化,因为它的每个字节都是0x3f
    const int INF = 0x3f3f3f3f;
    
    // 节点数与边数
    int N,R;
    
    struct edge
    {
        
        int to,cost;
    };
    // 这道题给的内存小，要用邻接表的，临接矩阵估计要超内存
    vector<edge> g[max_N];
    
    int d[max_N],d2[max_N];
    
    typedef pair<int,int> P;
    
    void Dijkstra(int x)
    {
        
        memset(d,0x3f,sizeof(d));
        memset(d2,0x3f,sizeof(d2));
        d[x]=0;
        // 默认建立最大堆，这里利用greater,建立最小堆
        // 这里建立的最小优先级队列，每次取出最小元素，复杂度log(n),n为队列中的元素个数
        priority_queue< P,vector<P>,greater<P> >  que;
        // 让第一个元素表示最短距离，第二个存储编号信息，即可实现按第一元素的排序
        // 无需再定义红黑树中的比较大小的函数
        que.push(P(0,x));
    
        while(!que.empty())
        {
        
            P p=que.top();
            que.pop();
            int len=p.first,num=p.second;
            // 剪枝
            // 取出的顶点已经被更新成更小的了，本次是无用的操作，直接跳过
            // 这道题写的很舒服啊，最短路嘛，从头到尾，一气呵成，然后运行，成功，试样例，过
            // 交!嗯？？wa了？咋回事呢？找了一边，发现是剪枝这里搞错了
            // 把这段代码去掉（其实不快多少，追求嘛,当然要有的），或者加了个2才对的
            // 因为这里如果对小于等于于d[num]之外的情况进行讨论，会把d2的许多可行更新给过滤掉
            // 其实不难，你懂的，多注意一下就好，还是得细心，交前还是得查代码的。
            if(len>d2[num])
            {
        
                continue;
            }
            for(int i=0;i<g[num].size();++i)
            {
        
                edge e=g[num][i];
                int now_d=len + e.cost;
                // 更新最短路
                if(d[e.to] > now_d)
                {
        
                    // 看可否通识更新次短路,次短路可以是之前的最短路啦
                    // 之前不能更新，因为要求的是次短路，但是现在也许可以更新了，所以要尝试一下。
                    swap(d[e.to],now_d);
                    que.push(P(d[e.to],e.to));
                }
                // 为什么会有后面这一条判断条件？
                // 之前的交换操作，保证了now_d不会比d[e.to]小，但没有不保证相等啊
                // 相等的话，也不能算是次短路吧，只能算另一条最短路而已，而我们只记录距离，不关心条数的
                if(d2[e.to]>now_d && d[e.to] <now_d)
                {
        
                    d2[e.to]=now_d;
                    // 为什么还要加到队列中，之前的那步添加不是已经是Dijkstra完整的更新过程了吗？
                    // 你要考虑的是，这不单单是一个Dijkstra,实际上，是两个，第二个是有限定的Dijkstra
                    // 两个之间的交叉部分，不会有影响，只是多增加了最多一倍的更新而已
                    // （大多上不到一倍吧，只是多一些，有些更新后，会直接在之前的剪枝操作中去掉了）
                    que.push(P(d2[e.to],e.to));
                }
            }
        }
    
        //printf("%d\n",d[N]);
        printf("%d\n",d2[N]);
    }
    
    int main()
    {
        
        scanf("%d %d",&N,&R);
        for(int i=0;i<R;++i)
        {
        
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            edge e1;
            e1.to=y;
            e1.cost=z;
            g[x].push_back(e1);
            edge e2;
            e2.to=x;
            e2.cost=z;
            g[y].push_back(e2);
        }
    
        Dijkstra(1);
    
        return 0;
    }

[Link 1]: http://poj.org/problem?id=3255
[20200305182822178.png]: https://img-blog.csdnimg.cn/20200305182822178.png
[20200305183236910.png]: https://img-blog.csdnimg.cn/20200305183236910.png