【题解】
这两道题是完全一样的。
思路其实很简单，对于两种边权分别建反向图跑dijkstra。
如果某条边在某一种边权的图中不是最短路上的边，就把它的cnt加上1。（这样每条边的cnt是0或1或2，代表经过这条边GPS报警的次数）
最后用每条边的cnt作为边权建图，跑dijkstra即可。
判断某条边是不是最短路上的边：建反向图，以n为起点跑dijkstra，如果某条边(u,v)满足dis[v]=dis[u]+w,那么这条边是u到n的最短路上的边。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define LL long long 5 #define rg register 6 #define N 200010 7 #define M 500010 8 using namespace std; 9 int n,m,tot,fa,son,last[N],dis[N],pos[N]; 10 struct edge{int to,pre,dis;}e[M]; 11 struct rec{int u,v,d1,d2,d3;}r[M]; 12 struct heap{int p,d;}h[N]; 13 inline int read(){ 14 int k=0,f=1; char c=getchar(); 15 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 16 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 17 return k*f; 18 } 19 inline void up(int x){ 20 while((fa=x>>1)&&h[fa].d>h[x].d) swap(h[fa],h[x]),swap(pos[h[fa].p],pos[h[x].p]),x=fa; 21 } 22 inline void down(int x){ 23 while((son=x<<1)<=tot){ 24 if(h[son+1].d<h[son].d&&son<tot) son++; 25 if(h[son].d<h[x].d) swap(h[son],h[x]),swap(pos[h[x].p],pos[h[son].p]),x=son; 26 else return; 27 } 28 } 29 inline void dijkstra(int x){ 30 for(rg int i=1;i<=n;i++) dis[i]=1e9; 31 h[tot=pos[x]=1]=(heap){x,dis[x]=0}; 32 while(tot){ 33 int now=h[1].p; pos[h[tot].p]=1; h[1]=h[tot--]; if(tot) down(1); 34 for(rg int i=last[now],to;i;i=e[i].pre)if(dis[to=e[i].to]>dis[now]+e[i].dis){ 35 dis[to]=dis[now]+e[i].dis; 36 if(!pos[to]) h[pos[to]=++tot]=(heap){to,dis[to]}; 37 else h[pos[to]].d=dis[to]; 38 up(pos[to]); 39 } 40 } 41 } 42 inline void Pre(){ 43 memset(last,0,sizeof(last)); 44 memset(pos,0,sizeof(pos)); 45 tot=0; 46 } 47 inline void work(){ 48 for(rg int i=1,u,v,d;i<=m;i++){ 49 u=r[i].u,v=r[i].v,d=r[i].d1; 50 e[++tot]=(edge){u,last[v],d}; last[v]=tot; 51 } 52 dijkstra(n); 53 for(rg int i=1;i<=m;i++) 54 if(dis[r[i].u]!=dis[r[i].v]+r[i].d1) r[i].d3++; 55 Pre(); 56 for(rg int i=1,u,v,d;i<=m;i++){ 57 u=r[i].u,v=r[i].v,d=r[i].d2; 58 e[++tot]=(edge){u,last[v],d}; last[v]=tot; 59 } 60 dijkstra(n); 61 for(rg int i=1;i<=m;i++) 62 if(dis[r[i].u]!=dis[r[i].v]+r[i].d2) r[i].d3++; 63 Pre(); 64 for(rg int i=1,u,v;i<=m;i++){ 65 u=r[i].u,v=r[i].v; 66 e[++tot]=(edge){u,last[v],r[i].d3}; last[v]=tot; 67 } 68 dijkstra(n); 69 } 70 int main(){ 71 n=read(); m=read(); 72 for(rg int i=1;i<=m;i++) 73 r[i].u=read(),r[i].v=read(),r[i].d1=read(),r[i].d2=read(); 74 work(); 75 printf("%d ",dis[1]); 76 return 0; 77 }