传送门
解题思路
简化一下题面：在 n 个点 m 条正权边的有向图中，共有 n 个⼈要执⾏任务，第 i 个⼈的路线为 1 → i → 1，求最⼩总路程。
这就很显然了，在原图中跑一遍单源最短路，求出所有1->的最短路，然后建一个反图，再跑一遍最短路，求出i到1的最短路，最后把答案加起来。
看看数据范围：1 ≤ n, m ≤ 10^6。
这很显然需要一个log的算法，用优先队列优化的dijkstra时间可能有点卡，所以我们用set优化dijkstra，就能过了。
当然，如果不怕被卡，你可以用spfa稳过。
AC代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxm=1000005; 4 int t,n,m,cnt[2],p[2][maxm]; 5 int dis[2][maxm]; 6 set<pair<int,int> > q; 7 struct node{ 8 int v,next,value; 9 }e[2][maxm]; 10 void insertt(int id,int u,int v,int value){ 11 cnt[id]++; 12 e[id][cnt[id]].v=v; 13 e[id][cnt[id]].next=p[id][u]; 14 e[id][cnt[id]].value=value; 15 p[id][u]=cnt[id]; 16 } 17 void dij(int id){ 18 q.clear(); 19 dis[id][1]=0; 20 q.insert(make_pair(0,1)); 21 while(!q.empty()){ 22 int u=q.begin()->second; 23 q.erase(q.begin()); 24 for(int i=p[id][u];i!=-1;i=e[id][i].next){ 25 int v=e[id][i].v,value=e[id][i].value; 26 if(dis[id][v]>dis[id][u]+value){ 27 q.erase(make_pair(dis[id][v],v)); 28 dis[id][v]=dis[id][u]+value; 29 q.insert(make_pair(dis[id][v],v)); 30 } 31 } 32 } 33 } 34 int main(){ 35 cin>>t; 36 while(t--){ 37 memset(p,-1,sizeof(p)); 38 memset(dis,0x3f,sizeof(dis)); 39 memset(e,0,sizeof(e)); 40 memset(cnt,0,sizeof(cnt)); 41 scanf("%d%d",&n,&m); 42 for(int i=1;i<=m;i++){ 43 int u,v,value; 44 scanf("%d%d%d",&u,&v,&value); 45 insertt(0,u,v,value); 46 insertt(1,v,u,value); 47 } 48 long long ans=0; 49 dij(0); 50 dij(1); 51 for(int id=0;id<=1;id++){ 52 for(int i=1;i<=n;i++){ 53 ans+=dis[id][i]; 54 } 55 } 56 printf("%lld ",ans); 57 } 58 return 0; 59 }