题面:https://www.luogu.org/problemnew/show/P3106

本题三次建图: 先将GPS1的图存入邻接表。跑一遍dijkstra

然后将GPS2的图再存入邻接表。再跑一遍dijkstra

最后将2次跑过的dijkstra,得到的最短路后所发出的警告数(分别不在2个Gps的次数)当成边权,再跑一遍dijstra。

Code:

#include<stdio.h>
#include <queue>
#include<iostream>
#include<cstring>
using namespace std;
int n,m,head[100005],j,Next[100005],adj1[100005],adj2[100005],adj3[100005],p,q,a,b,i,k,d[100005],d2[100005],lun[100005];
void Push(int u,int v,int w,int t)
{
    Next[++k]=head[u];
    head[u]=k;
    lun[k]=v;
    adj1[k]=w;
    adj2[k]=t;
}
struct str{
    int s,w;
};
bool operator <(str a,str b)
{
    return a.w>b.w;
}
int adj(int fl,int i)
{
    if(fl==1)
        return adj1[i];
    if(fl==2)
        return adj2[i];
    if(fl==3)
        return adj3[i];
}
void Dijkstra(int fl)
{
    int i,vis[100005]={0};
    memset(d,0x7f7f7f,sizeof(d));
    d[n]=0;
    priority_queue<str> q;
    q.push((str){n,0});
    while(!q.empty())
    {
        str p=q.top();
        q.pop();
        if(vis[p.s]!=0)
            continue;
        vis[p.s]=1;
        for(i=head[p.s];i!=0;i=Next[i])
            if(d[p.s]+adj(fl,i)<d[lun[i]])
            {
                d[lun[i]]=d[p.s]+adj(fl,i);
                q.push((str){lun[i],d[lun[i]]});
            }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d %d",&a,&b,&p,&q);
        Push(b,a,p,q);
    }
    Dijkstra(1);
    for(i=1;i<=n;i++)
        d2[i]=d[i];
    Dijkstra(2);
    for(i=1;i<=n;i++)
        for(j=head[i];j!=0;j=Next[j])
        {
            if(d2[i]+adj1[j]!=d2[lun[j]])
                adj3[j]++;
            if(d[i]+adj2[j]!=d[lun[j]])
                adj3[j]++;
        }
    Dijkstra(3);
    printf("%d",d[1]);
}