poj 3255 Roadblocks【次短路】

绝地灬酷狼 2022-08-06 00:21 75阅读 0赞

题目：[poj 3255 Roadblocks][]

题意：给出一个无向图，然后求1到n点的次短路

分析：两种做法，第一种，Astat+最短路求k短路的方法。

第二种是比较暴力的方法。

先求1点到所有点的最短路dis1

然后求n点到所有点的最短路dis2

然后枚举所有边，则次短路为dis1【from】 + dis2【to】 + w【i】中大于最短路的最短的。

AC代码：

#include <cstdio>
    #include <string>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    using namespace std;
    const int N = 5700;
    const int inf = 0x3f3f3f3f;
    struct Node
    {
        int to,val;
    };
    vector<Node> g[N],rg[N];
    int dis[N];
    bool vis[N];
    int n,m;
    void SPFA(int src)
    {
        int i;
        memset(dis,inf,sizeof(dis));
        dis[src] = 0;
        queue<int> Q;
        Q.push(src);
        while(!Q.empty())
        {
            int u,v;
            u = Q.front();
            Q.pop();
            for(int i = 0;i<g[u].size();i++)
            {
                v = g[u][i].to;
                if(dis[v]>dis[u]+g[u][i].val) //记得这里这样写  最后改一下vis
                {
                    dis[v] = dis[u] + g[u][i].val;
                    Q.push(v);
                }
            }
        }
    }
    int dis1[N];
    void SPFA1(int src)
    {
        int i;
        memset(dis1,inf,sizeof(dis1));
        dis1[src] = 0;
        queue<int> Q;
        Q.push(src);
        while(!Q.empty())
        {
            int u,v;
            u = Q.front();
            Q.pop();
            for(int i = 0;i<g[u].size();i++)
            {
                v = g[u][i].to;
                if(dis1[v]>dis1[u]+g[u][i].val) //记得这里这样写  最后改一下vis
                {
                    dis1[v] = dis1[u] + g[u][i].val;
                    Q.push(v);
                }
            }
        }
    }
    void Clear(int x)
    {
        for(int i=0;i<=x;i++){
            g[i].clear();
            rg[i].clear();
        }
    }
    int x[101000],y[101000],z[101000];
    int main()
    {
        //freopen("a.txt","r",stdin);
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=0;i<m;i++)
            {
                scanf("%d%d%d",&x[i],&y[i],&z[i]);
                g[y[i]].push_back((Node){x[i],z[i]});
                g[x[i]].push_back((Node){y[i],z[i]});
                rg[x[i]].push_back((Node){y[i],z[i]});
                rg[y[i]].push_back((Node){x[i],z[i]});
            }
            int s=1,t=n,k=2;
            SPFA(t);
            SPFA1(s);
            int mi = dis1[t];
            int ans = inf;
            for(int i=0;i<m;i++)
            {
                int tmp = dis[y[i]] + dis1[x[i]] + z[i];
                int css = dis[x[i]] + dis1[y[i]] + z[i];
                if(tmp>mi)
                    ans = min(ans,tmp);
                if(css>mi)
                    ans = min(ans,css);
            }
            printf("%d\n",ans);
            Clear(n);
        }
        return 0;
    }

[poj 3255 Roadblocks]: http://poj.org/problem?id=3255http://