P1629 邮递员送信（最短路+反向建边）

题目链接：邮递员送信 - 洛谷

这道题需要注意的一点是题目中所给的边是单向边，如果是双向边的话那么1到其他点所需的最短距离与从其他点回来的最短距离是相等的，就是我们只需要从1号点跑一个最短路，然后加上所有距离的二倍即可。

我们求的是1号点到其他所有点的最短距离的和+所有其他点到1号点的最短距离和，我们把答案分成这两部分求，先求1号点到其他所有点的最短距离的和，这个比较简单，就是从1号点跑一个最短路求出1号点到其他点的最短路及，然后就把他们加起来即可，关键是求所有其他点到1号点的最短距离和，我们不可能从每个点都跑一遍最短路，这样肯定是会超时的，这里就需要用一个技巧了，就是我们把所有的边反向建立，然后再从1号点跑一个最短路，这样再把1号点到所有点的最短距离加起来就得到了所有其他点到1号点的最短距离和，原理是什么呢？我们像，假如原来2到1有一条长度为5的边，而我们建反向边建立的是从1到2有一条长度为5的边，如果1到2的最短距离包含此条边，这时候最短路径中从1到2所走的每一步都是反向的，也就是说可以正好从2到1按照反向边走回来，所以这样就得到了最短距离。这个技巧比较巧妙，建议好好理解一下。

下面是代码：

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e6+10;
int h[N],w[N],e[N],ne[N],idx,d[N];
int u[N],v[N],t[N];
bool vis[N];
typedef pair PII;
void add(int x,int y,int z)
{e[idx]=y;w[idx]=z;ne[idx]=h[x];h[x]=idx++;
}
void dijkstra(int x)
{priority_queue,greater >q;memset(d,0x3f,sizeof d);d[x]=0;memset(vis,false,sizeof vis);q.push({d[x],x});while(!q.empty()){int begin=q.top().second;q.pop();if(vis[begin]) continue;vis[begin]=true;for(int i=h[begin];i!=-1;i=ne[i]){int j=e[i];if(d[j]>d[begin]+w[i]){d[j]=d[begin]+w[i];q.push({d[j],j});}}}
}
int main()
{int n,m;cin>>n>>m;memset(h,-1,sizeof h);for(int i=1;i<=m;i++){scanf("%d %d %d",&u[i],&v[i],&t[i]);add(u[i],v[i],t[i]);}dijkstra(1);long long ans=0;for(int i=1;i<=n;i++)ans+=d[i];idx=0;memset(h,-1,sizeof h);for(int i=1;i<=m;i++)add(v[i],u[i],t[i]);dijkstra(1);for(int i=1;i<=n;i++)ans+=d[i];printf("%lld",ans);return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！