题解 | 邮递员送信

由于邮递员只能一封一封地送信，为了使总时间最少，每次应该走最短路到达各个路口，然后从各个路口返回时也应走最短路回到邮局。但是由于道路是单向的，因此邮递员出发的时候是单源最短路，可以用堆优化版dijkstra算法计算最短路，而回来的时候是多源最短路，但我们可以反向思考，若建立的是反图，邮递员回邮局的路就变成了从邮局出发到各个路口的单源最短路，那此时也可用堆优化版dijkstra算法来计算。那么最后的答案为∑dist1[i]+dist2[i]，2<=i<=n，其中dist1为正向建图的dijkstra计算出的距离函数，而dist2为反向建图的dijkstra计算出的距离函数

实现：

我习惯下标从0开始；分析数据发现答案不会爆int；时间复杂度为$O(mlogn)$，不会超时。

正好最近也在学习Python，贴一份C++代码，再贴一份Python代码

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

using i64 = long long;
using pii = std::pair<int,int>;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int n,m;
  std::cin >> n >> m;

  std::vector<std::vector<pii>> adj1(n),adj2(n);
  for(int i = 0; i < m; i++){
    int u,v,w;
    std::cin >> u >> v >> w;
    u--,v--;

    adj1[u].push_back({v,w});
    adj2[v].push_back({u,w});
  }

  std::vector<bool> vis1(n),vis2(n);
  std::vector<int> dist1(n,1E9),dist2(n,1E9);
  auto dijkstra1 = [&](){
    std::priority_queue<pii,std::vector<pii>,std::greater<>> heap;
    dist1[0] = 0;
    heap.push({0,0});
    
    while(heap.size()){
      auto [distance,u] = heap.top();
      heap.pop();

      if(vis1[u]){
        continue;
      }
      vis1[u] = true;

      for(const auto& [v,w]:adj1[u]){
        if(distance+w < dist1[v]){
          dist1[v] = distance+w;
          heap.push({dist1[v],v});
        }
      }
    }
  };

  dijkstra1();

  auto dijkstra2 = [&](){
    std::priority_queue<pii,std::vector<pii>,std::greater<>> heap;

    dist2[0] = 0;
    heap.push({0,0});

    while(heap.size()){
      auto [distance,u] = heap.top();
      heap.pop();

      if(vis2[u]){
        continue;
      }
      vis2[u] = true;

      for(const auto& [v,w]:adj2[u]){
        if(distance+w < dist2[v]){
          dist2[v] = distance+w;
          heap.push({dist2[v],v});
        }
      }
    }
  };

  dijkstra2();

  i64 ans = 0;
  for(int i = 0; i < n; i++){
    ans += dist1[i]+dist2[i];
  }

  std::cout << ans << "\n";
}

import sys
import heapq

input = lambda : sys.stdin.readline().strip()

n,m = map(int,input().split())

adj1 = [[] for i in range(n)]
adj2 = [[] for i in range(n)]

for i in range(m):
  u,v,w = map(int,input().split())
  u -= 1
  v -= 1
  adj1[u].append((v,w))
  adj2[v].append((u,w))

dist1 = [10 ** 9] * n
dist2 = [10 ** 9] * n
vis1 = [False] * n
vis2 = [False] * n

heap1 = []
heap2 = []

dist1[0] = 0

heapq.heappush(heap1,(0,0))

while heap1:
  (distance,u) = heapq.heappop(heap1)
  if vis1[u]:
    continue
  vis1[u] = True

  for (v,w) in adj1[u]:
    if distance+w < dist1[v]:
      dist1[v] = distance+w
      heapq.heappush(heap1,(dist1[v],v))

heapq.heappush(heap2,(0,0))
while heap2:
  (distance,u) = heapq.heappop(heap2)
  if vis2[u]:
    continue
  vis2[u] = True

  for (v,w) in adj2[u]:
    if distance+w < dist2[v]:
      dist2[v] = distance+w
      heapq.heappush(heap2,(dist2[v],v))

ans = 0
for i in range(1,n):
  ans += dist1[i]+dist2[i]

print(ans)