Massive Algorithms: POJ 3255 -- Roadblocks

POJ 3255 -- Roadblocks

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

Sample Output

有N条道路和N个路口，道路是双向的，问1号路口到N号路口的次最短路径是多少？次最短路径是比最短路径长的次短的路径。同一条边可已经过多次。

http://www.cnblogs.com/whatbeg/p/3642231.html

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

#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;
}

http://blog.csdn.net/murmured/article/details/20577945

思路：

最短路和次短路不会重合，而次短路可以从最短路的某个点绕一个点得到。为啥是一个点？如果绕两个点的话会比绕一个点来的长，就不会是次短路了。

先对1和n为源点进行两次dijkstra，接下来枚举每条边，则可以算出此时的和temp=dis1[from]+disn[to]+val;或者temp=disn[from]+dis1[to]+val;如果不等于最短路则取最小值。

int n,r,head[MAXN],len,dis1[MAXN],disn[MAXN];
struct edge
{
int to,val,next;
}e[MAXM];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
struct node
{
int id,val;
node(int id,int val):id(id),val(val){}
bool operator < (const node &x)const{
return val>x.val;
}
};
void dijkstra(int *dis,int s)
{
for(int i=1;i<=n;i++)
dis[i]=INF;
dis[s]=0;
priority_queue<node> q;
q.push(node(s,0));
while(!q.empty())
{
int cur=q.top().id,val=q.top().val;
q.pop();
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[id] > dis[cur]+e[i].val)
{
dis[id]=dis[cur]+e[i].val;
q.push(node(id,dis[id]));
}
}
}
}
int main()
{
while(~scanf("%d%d",&n,&r))
{
memset(head,-1,sizeof(head));
len=0;
for(int i=0;i<r;i++)
{
int from,to,val;
scanf("%d%d%d",&from,&to,&val);
add(from,to,val);
add(to,from,val);
}
dijkstra(dis1,1);
dijkstra(disn,n);
//printf("%d %d\n",dis1[n],disn[1]);
int ans=INF;
for(int cur=1;cur<=n;cur++)
{
for(int i=head[cur];i!=-1;i=e[i].next)
{
int from=cur,to=e[i].to,val=e[i].val;
int temp=dis1[from]+disn[to]+val;
if(temp!=dis1[n] && temp <ans)
ans=temp;
temp=disn[from]+dis1[to]+val;
if(temp!=dis1[n] && temp <ans)
ans=temp;
}
}
printf("%d\n",ans);
}
return 0;
}

http://puyopop6.blogspot.com/2013/12/poj-3255-roadblocks.html

int N,R;

struct edge{int to, cost;};

typedef pair<int, int> P;

vector<edge> G[MAX_N];

int dist[MAX_N];

int dist2[MAX_N];

void solve(){

  priority_queue<P, vector<P>, greater<P> > pq;

  fill(dist, dist+N, INF);

  fill(dist2, dist2+N, INF);

  dist[0] = 0;

  pq.push(P(0, 0));

  while(!pq.empty()){

 P p = pq.top();

 if(DBG){

   cout << p.first << " " << p.second << endl;

}

 pq.pop();

 int v = p.second, d = p.first;

 if(dist2[v] < d){

   continue;

}

 for(int i = 0; i < G[v].size(); i++){

   edge &e = G[v][i];

   int d2 = d + e.cost;

   if(dist[e.to] > d2){

  swap(dist[e.to], d2);

  pq.push(P(dist[e.to], e.to));

}

   if(dist2[e.to] > d2){

  dist2[e.to] = d2;

  pq.push(P(dist2[e.to], e.to));

}

}

}

  cout << dist2[N-1] << endl;

}

int main(){

  cin >> N >> R;

  for(int i = 0; i < R; i++){

 int s,t,c;

 scanf("%d %d %d", &s, &t, &c);

 G[s-1].push_back((edge){t-1, c});

 G[t-1].push_back((edge){s-1, c});

}

  solve();

  return 0;

}

Read full article from 3255 -- Roadblocks

POJ 3255 -- Roadblocks

Labels

Popular Posts