D66 最短路+建反图 Dijkstra 算法 P1629 邮递员送信

// 最短路+建反图 Dijkstra 算法 O(mlogn)
#include<bits/stdc++.h>
#define pli pair<long long,int>
using namespace std;

const int N=2005;
int n,m;
vector<pli> e[N];
long long d[N];

void dijkstra(int s){
  memset(d,0x3f,sizeof d); d[s]=0;
  priority_queue<pli,vector<pli>,greater<pli> > q; //小根堆
  q.emplace(0,s);
  while(q.size()){
    auto [dd,u]=q.top(); q.pop();
    if(dd>d[u]) continue; //这个u不是第一次出队，不拓展
    for(auto [w,v]:e[u]){
      if(d[v]>d[u]+w) q.emplace(d[v]=d[u]+w,v);
    }
  }
}
int main(){
  cin>>n>>m;
  for(int i=0,u,v,w; i<m; i++){
    cin>>u>>v>>w;
    e[u].emplace_back(w,v);     //建图
    e[v+n].emplace_back(w,u+n); //建反图
  }
  
  long long ans=0;
  dijkstra(1);
  for(int i=2; i<=n; ++i) ans+=d[i]; //1到各点的最短路之和
  dijkstra(1+n);
  for(int i=2+n; i<=n<<1; ++i) ans+=d[i]; //各点到1的最短路之和
  printf("%lld",ans);
}