这道题很适合作为P1629的加强版

因为这道题其实体现了反向建图的高效性

反向建图后：

单终点最短路径→单源最短路径。

因此两边Dij，然后再累计和即可

代码部分不难弄。直接上

先说明以下程序，有1的变量名与第一次dij有关（学生出来）

带2的与第二次dij有关（学生回家）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int n,m;int h1[2100000],h2[2100000];int s1,s2;struct edge{int next,to,dis;};int v1[2100000],v2[2100000]; //注意数据范围long long d1[2100000],d2[2100000];edge e1[2100000],e2[2100000];void addedge1(int next,int to,long long dis){e1[++s1].dis=dis;e1[s1].next=h1[next];e1[s1].to=to;h1[next]=s1;}void addedge2(int next,int to,long long dis){e2[++s2].dis=dis;e2[s2].to=to;e2[s2].next=h2[next];h2[next]=s2;}void dij1(int start){priority_queue 
          
           
             > q; //这是优先队列的一个比较容易理解的写法，之所以long long 是因为可总和可能爆intmemset(d1,0x3f,sizeof(d1));memset(v1,0,sizeof(v1));q.push(make_pair(0,start));d1[1]=0;while(!q.empty()){int i,j;long long k;int t=q.top().second;q.pop();if(v1[t]) continue;v1[t]=1;for(i=h1[t];i;i=e1[i].next){j=e1[i].to;k=e1[i].dis;if(d1[t]+k
            
              > q; memset(d2,0x3f,sizeof(d2));memset(v2,0,sizeof(v2));q.push(make_pair(0,start));d2[1]=0;while(!q.empty()){int i,j;long long k;int t=q.top().second;q.pop();if(v2[t]) continue;v2[t]=1;for(i=h2[t];i;i=e2[i].next){j=e2[i].to;k=e2[i].dis;if(d2[t]+k