【POJ 3255】Roadblocks

Roadblocks
一句话题意
问你严格意义的第二短路。
题解:
从1出发,求出到每个点的最短路,从N出发求出到每个点的最短路。

然后枚举每一条路,然后枚举经过的这条边的路径长度,然后比较得出严格第二短路(一定要大于最短路)。

哈哈哈哈哈,透露一下,这个代码是我一边打炉石一边写的,最后1A了,似乎有点败人品。。。。。

代码

#include <iostream>
#include <cstdio>
#include <queue>

const int MAXN = 5005,MAXX = 1000005,INF = 200000000;

using namespace std;

int n,r,e = 1,Min,Mins;
int d_s[MAXN],d_e[MAXN],head[MAXN];
bool inq[MAXN];

queue<int>q;

struct node{
    int v,c,next;
}edge[MAXX];

inline int read()
{
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <=ch && ch <='9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

inline void addedge(int u,int v,int c){
    edge[e] = (node){v,c,head[u]};head[u] = e++;
    edge[e] = (node){u,c,head[v]};head[v] = e++;    
}

inline void init()
{
    n = read();r = read();
    
    int u,v,c;
    
    for(int i = 1;i <= r;i++){
        u = read();v = read();c = read();
        addedge(u,v,c);
    }
    
}

inline void spfa_s()
{
    for(int i = 1;i <= n;i++) d_s[i] = INF;
    
    d_s[1] = 0;q.push(1);inq[1] = true;
    
    int u,v,c;
    
    while(!q.empty()){
        u = q.front();q.pop();inq[u] = false;
        for(int i = head[u];i;i = edge[i].next){
            v = edge[i].v;c = edge[i].c;
            if(d_s[v] > d_s[u] + c){
                d_s[v] = d_s[u] + c;
                if(!inq[v]) q.push(v),inq[v] = true;
            }
        }
    }
}

inline void spfa_e()
{
    for(int i = 1;i <= n;i++) d_e[i] = INF;
    
    d_e[n] = 0;q.push(n);inq[n] = true;
    
    int u,v,c;
    
    while(!q.empty()){
        u = q.front();q.pop();inq[u] = false;
        for(int i = head[u];i;i = edge[i].next){
            v = edge[i].v;c = edge[i].c;
            if(d_e[v] > d_e[u] + c){
                d_e[v] = d_e[u] + c;
                if(!inq[v]) q.push(v),inq[v] = true;
            }
        }
    }
}

int main()
{
    init();
    spfa_s();
    spfa_e();
    
    Min = Mins = INF;
    
    int v,c;

    for(int i = 1;i <= n;i++)
    {
        for(int j = head[i];j;j = edge[j].next)
        {
            v = edge[j].v;c = edge[j].c;
            if(Min > d_s[i] + d_e[v] + c){
                Mins = Min;
                Min = d_s[i] + d_e[v] + c;
                continue;
            }
            if(Mins > d_s[i] + d_e[v] + c && d_s[i] + d_e[v] + c != Min){
                Mins = d_s[i] + d_e[v] + c;
            }
        }
    }
    
    printf("%d",Mins);
    
    return 0;
} 
Last modification:October 1st, 2018 at 08:10 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment