POJ3255Roadblocks[次短路]

32MS NO.1 #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cstring> using namespace std; const int N=5005,M=100005,INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x; } int n,m,u,v,w; struct edge{ int v,w,ne; }e[M<<1]; int h[N],cnt=0; inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt; } int d[N][2],inq[N],q[N],head=1,tail=0; void spfa(){ for(int i=1;i<=n;i++){d[i][0]=d[i][1]=INF;} d[1][0]=0; inq[1]=1; q[++tail]=1; while(head<=tail){ int u=q[head++];//printf("u %d\n",u); inq[u]=0; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v,w=e[i].w; if(d[v][0]>d[u][0]+w){ d[v][1]=d[v][0]; d[v][0]=d[u][0]+w; if(!inq[v]){inq[v]=1;q[++tail]=v;} }else if(d[v][1]>d[u][0]+w&&d[v][0]<d[u][0]+w){ d[v][1]=d[u][0]+w; if(!inq[v]){inq[v]=1;q[++tail]=v;} } if(d[v][1]>d[u][1]+w){ d[v][1]=d[u][1]+w; if(!inq[v]){inq[v]=1;q[++tail]=v;} } } } } int main(int argc, const char * argv[]) { n=read();m=read(); for(int i=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);} spfa(); printf("%d",d[n][1]); return 0; }

 

//dijkstra 63MS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int N=5005,M=100005,INF=1e9;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x;
}
int n,m,u,v,w;
struct edge{
    int v,w,ne;
}e[M<<1];
int h[N],cnt=0;
inline void ins(int u,int v,int w){
    cnt++;
    e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
    cnt++;
    e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}
int d[N][2],vis[N][2];
struct hn{
    int u,d,p;
    hn(int a=0,int b=0,int c=0):u(a),d(b),p(c){}
    bool operator < (const hn &rhs)const{return d>rhs.d;}
};
priority_queue<hn> q;
void dijkstra(){
    for(int i=1;i<=n;i++) {d[i][0]=d[i][1]=INF;}
    q.push(hn(1,0,0));
    d[1][0]=0;
    while(!q.empty()){
        hn now=q.top();q.pop();
        int u=now.u,p=now.p; 
        if(vis[u][p]) continue;
        vis[u][p]=1;
        for(int i=h[u];i;i=e[i].ne){
            int v=e[i].v,w=e[i].w;
            if(d[v][0]>d[u][p]+w){
                d[v][1]=d[v][0];
                d[v][0]=d[u][p]+w;
                q.push(hn(v,d[v][0],0));
                q.push(hn(v,d[v][1],1));
            }else if(d[v][1]>d[u][p]+w){
                d[v][1]=d[u][p]+w;
                 q.push(hn(v,d[v][1],1));
            }    
        }        
    }
}
int main(int argc, const char * argv[]) {
    n=read();m=read();
    for(int i=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}
    dijkstra();
    printf("%d",d[n][1]);
    return 0;
}

 

POJ3255Roadblocks[次短路]

标签：