POJ 3255 Roadblocks --次短路径

由于次短路一定存在,则可知次短路一定是最短路中某一条边不走,然后回到最短路,而且只是一条边,两条边以上不走的话,就一定不会是次短路了(即以边换边才能使最小)。所以可以枚举每一条边,算出从起点到这条边起点的最短距离,以及从终点到这条边终点的最短距离,再加上这条边的权值,看是否是次短路(比最短路总权值大的最小权值的路径)

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#define Mod 1000000007
using namespace std;
#define N 5007

vector<pair<int,int> > G[200005];
int ds[N],dt[N],vis[N];
int n,m,k;

void SPFA(int s,int *d)
{
    int i,u,v;
    queue<int> que;
    memset(vis,0,sizeof(vis));
    d[s] = 0;
    vis[s] = 1;
    que.push(s);
    while(!que.empty())
    {
        v = que.front();
        que.pop();
        vis[v] = 0;  //边允许重复走
        for(i=0;i<G[v].size();i++)
        {
            u = G[v][i].first;
            if(d[v] + G[v][i].second < d[u])
            {
                d[u] = d[v] + G[v][i].second;
                if(!vis[u])
                {
                    vis[u] = 1;
                    que.push(u);
                }
            }
        }
    }
}

int main()
{
    int u,v,w;
    int res,tmp,i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<n;i++)
            G[i].clear();
        for(i=1;i<=n;i++)
            ds[i] = dt[i] = Mod;
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            G[u].push_back(make_pair(v,w));
            G[v].push_back(make_pair(u,w));
        }
        SPFA(1,ds);
        SPFA(n,dt);
        res = Mod;
        for(i=1;i<=n;i++)
            for(j=0;j<G[i].size();j++)
            {
                u = i;
                v = G[i][j].first;
                w = G[i][j].second;
                tmp = ds[u] + dt[v] + w;
                if(tmp > ds[n] && res > tmp)
                    res = tmp;
            }
        printf("%d\n",res);
    }
    return 0;
}
View Code

 

POJ 3255 Roadblocks --次短路径,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。