题目
Luogu P1629 邮递员送信
分析
浏览一遍题目，很容易分析出是最短路模型。首先跑一次1号店到其他点的最短路，然后在他返回时从每一个点都跑一次最短路，但在返回过程中我们只利用每个点到1号点的最短路，却要跑(n-1)次，所以显然十分浪费。并且复杂度是O(n*m log n），爆炸。
如何解决这个问题呢？
如果我们把每条边的方向反过来，那么原来每个点到1的最短路就变成了1到每个点的最短路，相当于我们把路反着走了。由于边权没有改变，所以答案是正确的。于是我们把单源最短路+单汇最短路的模型转化为了两次单源最短路！
实现起来也非常方便，只需要把每条边储存起来，在输入时先加原边，然后跑一次求出到每个点的最短路，接着清空边表加入反向边，再跑一次求出每次他回来时的最短路。将两次的答案加起来，就是最终结果了。时间复杂度就是O(2*m log n)。（使用堆优化dijkstra）
代码
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100002,inf=2147483647;
struct Edge{int to,next,v;
}e[maxn*2];
struct Node{int a,b;bool operator < (const Node &A) const{return b>A.b;}
};
int from[maxn],to[maxn],val[maxn],head[maxn],dis[maxn];
bool vis[maxn];
priority_queue<Node>q;
int n,m,cnt;
long long ans;
void add(int u,int v,int w)
{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;
}
void dijkstra()
{for(int i=1;i<=n;i++)dis[i]=inf;dis[1]=0;q.push((Node){
1,0});while(!q.empty()){Node u=q.top();q.pop();if(vis[u.a]) continue;vis[u.a]=1;for(int i=head[u.a];i;i=e[i].next){int v=e[i].to;if(dis[v]>dis[u.a]+e[i].v){dis[v]=dis[u.a]+e[i].v;q.push((Node){v,dis[v]});}}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&from[i],&to[i],&val[i]);add(from[i],to[i],val[i]);}dijkstra();for(int i=2;i<=n;i++)ans+=dis[i];memset(vis,0,sizeof(vis));memset(head,0,sizeof(head));cnt=0;//不要忘记清空有关变量和数组！！for(int i=1;i<=m;i++)add(to[i],from[i],val[i]);dijkstra();for(int i=2;i<=n;i++)ans+=dis[i];printf("%lld",ans);return 0;
}