图论模拟题。
这题直接写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 500005using 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;}
