【洛谷P3106】Dueling GPSs S【最短路 变式】

$Problemlink$

分析：

以$n$为起点 跑两次$spfa$ 记录两个$GPS$的最短路径
最后再做一遍$spfa$

对于统计不在最短路上 可以先建边权为$2$的图 跑最短路 遇到相同的$-1$即可

CODE：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct Edge{int to,next,k;
}a[N],b[N],c[N];
int n,m,tot,tot2,tot3;
int head[N],head2[N],head3[N],dis[N],dis2[N],dis3[N],id[N],id2[N];
bool vis[N];
queue<int> q,clear;
void add(int x,int y,int k,int &cnt,Edge edge[],int head[])
{edge[++cnt]=(Edge){y,head[x],k};head[x]=cnt;
}
void spfa(int st,Edge a[],int head[],int dis[],int id[])
{q=clear;memset(vis,0,sizeof vis);for(int i=1;i<=n;i++)dis[i]=0x7fffffff;q.push(st);vis[st]=1;dis[st]=0;while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=head[x];i;i=a[i].next){int qwq=a[i].to;if(dis[qwq]>dis[x]+a[i].k){dis[qwq]=dis[x]+a[i].k;id[qwq]=i;if(!vis[qwq]){vis[qwq]=1;q.push(qwq);}}}}
}
void spfa2(int st)
{q=clear;memset(vis,0,sizeof vis);memset(dis3,0x7f,sizeof dis3);dis3[st]=0;vis[st]=1;q.push(st);while(!q.empty()){int x=q.front();q.pop();vis[x]=0;for(int i=head3[x];i;i=c[i].next){int qwq=c[i].to,k=c[i].k;if(id[x]==i) k--;if(id2[x]==i) k--;if(dis3[qwq]>dis3[x]+k){dis3[qwq]=dis3[x]+k;if(!vis[qwq]){vis[qwq]=1;q.push(qwq);}}}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1,x,y,p,q;i<=m;i++){scanf("%d%d%d%d",&x,&y,&p,&q);add(y,x,p,tot,a,head);add(y,x,q,tot2,b,head2);add(x,y,2,tot3,c,head3);}spfa(n,a,head,dis,id);spfa(n,b,head2,dis2,id2);spfa2(1);printf("%d",dis3[n]);return 0;
}