POJ - 3255 Roadblocks

困扰了两天的次短路问题终于在大佬 @C2013ZDX 的帮助下AC了。激动人心😂

传送门:戳我

题目大意:一张无向图,n个点,r条边,求起点1到终点n的次短路。

 

看到题目的时候就懵逼了,最短路好打,可是次短路是什么东东。

后来看了网上的题解,次短路应该是在一段最短路的基础上再加上一段次短路,证明过程不详讲,只要用spfa或dijkstra在记录最短路的时候顺便更新每个点的次短路即可。

 

早上打了个spfa,有时间可以尝试下dijkstra;

由于是无向图所以可以来回走,刚开始没注意到这么gay的条件导致次短路挂掉。。

 

下为code+手打注释

 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;

const int R=100010;
const int N=5010;

struct dist
{
    int first,second;
    dist()  {
        first = (int)1e9;
        second = (int)1e9;
    }
}dis[N];

int num[2*R],next[2*R],val[2*R],f[N],to[2*R],tot;

queue <int> q;

void adde(int u,int v,int w)    //邻接表
{
    next[++tot]=f[u];
    f[u]=tot;
    to[tot]=v;
    val[tot]=w;
}

void spfa(void)
{
    dis[1].first=0; //1的最短路清零,次短路不能
    q.push(1);
    while (!q.empty())
    {
        int nxt;
        int now=q.front();
        q.pop();
        for (int i=f[now];i;i=next[i])
        {
            int com=dis[now].first+val[i];  //1.起点到now点最短路+到to[i]的距离
            if (com<dis[nxt = to[i]].first)     //更新最短路
            {
                int tem=dis[nxt].first;
                dis[nxt].first=com;
                dis[nxt].second=tem;    //原最短路更新为次短路
                q.push(nxt);
            }
            if (com>dis[nxt].first && com<dis[nxt].second)  //更新次短路
            {
                dis[nxt].second=com;
                q.push(nxt);
            }
            com=dis[now].second+val[i]; //2.起点到now点的次短路加上到to[i]点的距离
            if (com>dis[nxt].first && com<dis[nxt].second)  //更新次短路*2
            {
                dis[nxt].second=com;
                q.push(nxt);
            }
        }
    }
}

int main(void)
{
    int n,m,u,v,w;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        adde(u,v,w);
        adde(v,u,w);    //无向图
    }
    spfa();
    printf("%d\n",dis[n].second);
    return 0;
}

 

看到图论就脸黑,还是太过年轻🤣

 

岂曰无衣,与子同袍。

Y.W.             2017/7/11       东海集训

发表评论

电子邮件地址不会被公开。 必填项已用*标注