题面:

本题三次建图:先将GPS1的图存入邻接表。跑一遍dijkstra然后将GPS2的图再存入邻接表。再跑一遍dijkstra最后将2次跑过的dijkstra,得到的最短路后所发出的警告数(分别不在2个Gps的次数)当成边权,再跑一遍dijstra。Code:#include
    
     #include 
     
      #include
      
       #include
       
        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
        
          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)