浏览一遍题目,很容易分析出是最短路模型。首先跑一次1号店到其他点的最短路,然后在他返回时从每一个点都跑一次最短路,但在返回过程中我们只利用每个点到1号点的最短路,却要跑(n-1)次,所以显然十分浪费。并且复杂度是O(n*m log n),爆炸。
如何解决这个问题呢?
如果我们把每条边的方向反过来,那么原来每个点到1的最短路就变成了1到每个点的最短路,相当于我们把路反着走了。由于边权没有改变,所以答案是正确的。于是我们把单源最短路+单汇最短路的模型转化为了两次单源最短路!
实现起来也非常方便,只需要把每条边储存起来,在输入时先加原边,然后跑一次求出到每个点的最短路,接着清空边表加入反向边,再跑一次求出每次他回来时的最短路。将两次的答案加起来,就是最终结果了。时间复杂度就是O(2*m log n)。(使用堆优化dijkstra)
#include#include #include #include 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 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; }