P1629 邮递员送信

题目描述

有一个邮递员要送东西，邮局在节点 $1$。他总共要送 $n-1$ 样东西，其目的地分别是节点 $2$ 到节点 $n$。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 $m$ 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 $n-1$ 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数，$n$ 和 $m$，表示城市的节点数量和道路数量。

第二行到第 $(m+1)$ 行，每行三个整数，$u,v,w$，表示从 $u$ 到 $v$ 有一条通过时间为 $w$ 的道路。

输出格式

输出仅一行，包含一个整数，为最少需要的时间。

输入输出样例 #1

输入 #1

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

输出 #1

83

说明/提示

对于 $30\%$ 的数据，$1\le n\le 200$。

对于 $100\%$ 的数据，$1\le n\le 10^3$，$1\le m\le 10^5$，$1\le u,v\le n$，$1\le w\le 10^4$，输入保证任意两点都能互相到达。

C++实现

#include<bits/stdc++.h>
using namespace std;
const int INF=99999999;
int n,m;
int u[100005],v[100005],w[100005];
int dis[1005];
void init(){//初始化
scanf(“%d%d”,&n,&m);
for(int i=1;i<=m;i++)scanf(“%d%d%d”,&u[i],&v[i],&w[i]);
}
void over(){
for(int i=1;i<=m;i++){
swap(u[i],v[i]);
}
}
void ford(){//标准bellman-ford模板
for(int i=1;i<=n;i++)dis[i]=INF;
dis[1]=0;
for(int k=1;k<=n-1;k++){
for(int i=1;i<=m;i++){
if(dis[v[i]]>dis[u[i]]+w[i]){
dis[v[i]]=dis[u[i]]+w[i];
}
}
}
}
int main(){
init();
int ans=0;
ford();//跑最短路
for(int i=1;i<=n;i++)ans+=dis[i];//从一到多
over();//反转，反向建边
ford();//跑最短路
for(int i=1;i<=n;i++)ans+=dis[i];//从多到一
printf(“%d\n”,ans);
return 0;//完结撒花
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容