好久不写图论题了，Dijkstra都花了好长时间捡起来……之前也没有接触过反图的概念。这个题算是我重拾图论知识以来的第一题了。__φ(．．)
Dijkstra是单源最短路的算法。但这个题除了要求节点\(1\)到其他节点的距离，还要知道其他节点回到节点\(1\)的距离。如果我们每个点都跑一遍Dijkstra，时间复杂度是\(O(n(n \log n+m))\)，即使用堆优化也会超时。怎么解决呢？
我们可以额外建一个图，和原图相同，只不过所有边都反向了（原图的反图）。这样从\(1\)开始跑一遍单源最短路，其他节点回到\(1\)的距离就算出来了！
为了方便操作，我们把两个图存在一起，反图节点从\(n+1\)开始存。这里使用邻接表，注意存边的\(G\)数组、距离\(dis\)数组都要开\(2\)倍大小。从\(1\)和\(n+1\)各跑一次Dijkstra，最后把所有距离相加就是结果了。总时间复杂度\(O(n \log n+m)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,w;
};
vector<edge> G[2010];
int n,m,dis[2020];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
void dijkstra(int start){
q.push({0,start});
dis[start]=0;
while(!q.empty()){
auto p=q.top();
int v=p.second;
q.pop();
int len=G[v].size();
for(int i=0;i<len;i++){
edge e=G[v][i];
if(dis[e.to]>dis[v]+e.w){
dis[e.to]=dis[v]+e.w;
q.push({dis[e.to],e.to});
}
}
}
}
int main(){
memset(dis,127,sizeof dis);
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
edge e;
e.to=b,e.w=c;
G[a].push_back(e);
e.to=a+n;
G[b+n].push_back(e);
}
dijkstra(1);
dijkstra(n+1);
int ans=0;
for(int i=1;i<=2*n;i++) ans+=dis[i];
cout<<ans;
return 0;
}