poj 3255 Roadblocks 题解

发表于 | 更新于 | 阅读次数：
本文字数： 633 字 | 阅读时长 ≈ 3 分钟

题意简述

给你一个点边都1e5的图，求1到n的次短路。就是除了最短路之外最短的路。边珂以重复经过。

思路框架

搞Dijkstra的时候顺便维护次短即珂。

代码

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93

#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;namespace Flandre_Scarlet
{    #define N 14444    #define F(i,l,r) for(int i=l;i<=r;++i)    #define D(i,r,l) for(int i=r;i>=l;--i)    #define Fs(i,l,r,c) for(int i=l;i<=r;c)    #define Ds(i,r,l,c) for(int i=r;i>=l;c)    #define MEM(x,a) memset(x,a,sizeof(x))    #define FK(x) MEM(x,0)    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))    #define p_b push_back
    #define sz(a) ((int)a.size())    #define iter(a,p) (a.begin()+p)
    class Graph
    {
        public:
            int head[N];
            int EdgeCount;
            struct Edge
            {
                int To,Label,Next;
            }Ed[255555];
            void clear(int _V=N,int _E=N<<1) 
            {
                memset(Ed,-1,sizeof(Edge)*(_E));
                memset(head,-1,sizeof(int)*(_V));
                EdgeCount=-1;
            }
            void AddEdge(int u,int v,int w=1)
            {
                Ed[++EdgeCount]=(Edge){v,w,head[u]};
                head[u]=EdgeCount;
            }
            void Add2(int u,int v,int w=1) {AddEdge(u,v,w);AddEdge(v,u,w);}
            int Start(int u) {return head[u];}
            int To(int u){return Ed[u].To;}
            int Label(int u){return Ed[u].Label;}
            int Next(int u){return Ed[u].Next;}
    }G;
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int n,m;
    void Input()
    {
        G.clear();
        F(i,1,m)
        {
            int u,v,w;R1(u),R1(v),R1(w);
            G.Add2(u,v,w);
        }
    }

    struct node{int v,w;}; bool operator<(node a,node b){return a.w>b.w;}
    priority_queue<node> Q;
    int dis[N],dis2[N],vis[N];
    void Dijkstra()
    {
        while(!Q.empty()) Q.pop();
        MEM(dis,0x3f);MEM(dis2,0x3f);FK(vis);dis[1]=0;
        Q.push((node){1,0});
        while(!Q.empty())
        {
            node Min=Q.top();Q.pop();
            int u=Min.v;
            // if (vis[u]) continue;
            // vis[u]=1;
            // 不需要判vis，因为次短路珂能会被多次经过
            Tra(i,u)
            {int v=__v,w=G.Label(i);
                bool add=0;
                if (dis[u]+w<dis[v]) dis[v]=dis[u]+w,add=1;
                if (dis2[u]+w<dis2[v]) dis2[v]=dis2[u]+w,add=1;
                if (dis[u]+w>dis[v] and dis[u]+w<dis2[v]) dis2[v]=dis[u]+w,add=1;
                //只有这里被改了
                
                if (add) Q.push((node){v,dis[v]});
            }
        }
    }
    void Soviet()
    {
        Dijkstra();
        printf("%d\n",dis2[n]);
    }

    #define Flan void
    Flan IsMyWife()
    {
        while(~scanf("%d%d",&n,&m) and n+m)
        {
            Input();
            Soviet();
        }
    }}int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;}
w