洛谷1629题：邮差投递邮件

#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;
}