2018.07.22 洛谷P3106 GPS的决斗Dueling GPS's（最短路）

传送门

图论模拟题。

这题直接写3个（可以压成一个）spfa" role="presentation" style="position: relative;">spfaspfa，前两个把题上的p,q" role="presentation" style="position: relative;">p,qp,q分别当做边权来跑，然后最后一次将前两次标记过两次的边边权设为0，标记过一次的边权设为1，没标记过的边权设为0就行了。

代码如下：

#include<bits/stdc++.h>
#define N 100005
#define M 500005
using namespace std;
struct Node{int v,next,w;}e1[M<<1],e2[M<<1],e[M<<1];
int first1[N],first2[N],first[N],d1[N],d2[N],p1[N],p2[N],d[N],n,m,cnt=0,cnt1=0,cnt2=0;
bool in1[N],in2[N],in[N];
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
inline void add1(int u,int v,int w){
    e1[++cnt1].v=v;
    e1[cnt1].w=w;
    e1[cnt1].next=first1[u];
    first1[u]=cnt1;
}
inline void add2(int u,int v,int w){
    e2[++cnt2].v=v;
    e2[cnt2].w=w;
    e2[cnt2].next=first2[u];
    first2[u]=cnt2;
}
inline void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=first[u];
    first[u]=cnt;
}
inline void spfa1(int s=n){
    queue<int>q;
    memset(d1,0x3f3f3f3f,sizeof(d1));
    memset(in1,false,sizeof(in1));
    d1[s]=0,q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        in1[x]=false;
        for(int i=first1[x];i;i=e1[i].next){
            int v=e1[i].v;
            if(d1[v]>d1[x]+e1[i].w){
                d1[v]=d1[x]+e1[i].w;
                p1[v]=i;
                if(!in1[v])in1[v]=true,q.push(v);
            }
        }
    }
}
inline void spfa2(int s=n){
    queue<int>q;
    memset(d2,0x3f3f3f3f,sizeof(d2));
    memset(in2,false,sizeof(in2));
    d2[s]=0,q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        in2[x]=false;
        for(int i=first2[x];i;i=e2[i].next){
            int v=e2[i].v;
            if(d2[v]>d2[x]+e2[i].w){
                d2[v]=d2[x]+e2[i].w;
                p2[v]=i;
                if(!in2[v])in2[v]=true,q.push(v);
            }
        }
    }
}
inline void spfa(int s=1){
    queue<int>q;
    memset(d,0x3f3f3f3f,sizeof(d));
    memset(in,false,sizeof(in));
    d[s]=0,q.push(s);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        in[x]=false;
        for(int i=first[x];i;i=e[i].next){
            int v=e[i].v,w=e[i].w;
            if(p1[x]==i)--w;
            if(p2[x]==i)--w;
            if(d[v]>d[x]+w){
                d[v]=d[x]+w;
                if(!in[v])in[v]=true,q.push(v);
            }
        }
    }
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),p=read(),q=read();
        add1(v,u,p),add2(v,u,q),add(u,v,2);
    }
    spfa1(),spfa2(),spfa();
    printf("%d",d[n]);
    return 0;
}

巴特西

2018.07.22 洛谷P3106 GPS的决斗Dueling GPS's（最短路）

最新文章

热门文章