邮递员送信（洛谷1629）

​​传送门​​​ 第一反应是Floyd，但是看看数据规模，会tle
那就考虑n次单源最短路，但是即使是SPFA，也会t
那肯定就另有玄机。
我们每次出去送货后都要直接返回邮局，所以我们需要的信息是，从邮局到每一点的最短距离，和每一点到邮局的最短距离。无论是Floyd还是n次单源最短路，都求了很多无用的信息，即不同目的地之间的最短路，那是我们不需要的。这就会浪费时间。
所以我们应该怎么精确地求出自己所需要的信息呢？我们会发现无论是从邮局出去还是从外面回邮局，都有一个核心的汇聚点就是邮局，其实这就是两个单源最短路，一个是正的，一个是反的，所以我们只需要在建图时建造两张图，一张是正的，一张是反的，然后两边SPFA即可。
代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn=1005;
struct Edge{
  int from,to,dist;
  Edge(int u,int v,int d):from(u),to(v),dist(d){}
};
int n,m;
int d1[maxn];
int inq[maxn],cnt[maxn];
vector<Edge> edge;
vector<int> G[maxn];
queue<int> Q;
void Bellmanford(int s){
  memset(inq,0,sizeof(inq));
  memset(cnt,0,sizeof(cnt));
  memset(d1,0x3f,sizeof(d1));
  d1[s]=0;
  Q.push(s);
  inq[s]=1;
  while(!Q.empty()){
    int xx=Q.front();
    Q.pop();
    inq[xx]=0;
    for(int i=0;i<G[xx].size();i++){
      Edge e=edge[G[xx][i]];
      if(d1[e.to]>d1[xx]+e.dist){
        d1[e.to]=d1[xx]+e.dist;
        if(!inq[e.to]){
          Q.push(e.to);
          inq[e.to]=1;
          cnt[e.to]++;
          if(cnt[e.to]>n){
            return;
          }
        }
      }
    }
  }
} 
int d2[maxn];
vector<Edge> edge1;
vector<int> G1[maxn];
void antiBellmanford(int s){
  memset(inq,0,sizeof(inq));
  memset(cnt,0,sizeof(cnt));
  memset(d2,0x3f,sizeof(d2));
  d2[s]=0;
  Q.push(s);
  inq[s]=1;
  while(!Q.empty()){
    int xx=Q.front();
    Q.pop();
    inq[xx]=0;
    for(int i=0;i<G1[xx].size();i++){
      Edge e=edge1[G1[xx][i]];
      if(d2[e.to]>d2[xx]+e.dist){
        d2[e.to]=d2[xx]+e.dist;
        if(!inq[e.to]){
          Q.push(e.to);
          inq[e.to]=1;
          cnt[e.to]++;
          if(cnt[e.to]>n){
            return;
          }
        }
      }
    }
  }
} 
int main(){
  scanf("%d%d",&n,&m);
  int ind=1;
  for(int i=0;i<m;i++){
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    edge.push_back(Edge(u,v,w));
    G[u].push_back(i);
    edge1.push_back(Edge(v,u,w));
    G1[v].push_back(i);
  }
  Bellmanford(1);
  antiBellmanford(1);
  int ans=0;
  for(int i=2;i<=n;i++){
    ans+=d1[i]+d2[i];
  }printf("%d",ans);
  return 0; 
}