营销网站的建设与管理包括哪些事项,个人如何申请开公司,开发企业网关,wordpress 代码编辑器插件邮递员送信
题目描述
有一个邮递员要送东西#xff0c;邮局在节点 1 1 1。他总共要送 n − 1 n-1 n−1 样东西#xff0c;其目的地分别是节点 2 2 2 到节点 n n n。由于这个城市的交通比较繁忙#xff0c;因此所有的道路都是单行的#xff0c;共有 m m m 条道路。这…邮递员送信
题目描述
有一个邮递员要送东西邮局在节点 1 1 1。他总共要送 n − 1 n-1 n−1 样东西其目的地分别是节点 2 2 2 到节点 n n n。由于这个城市的交通比较繁忙因此所有的道路都是单行的共有 m m m 条道路。这个邮递员每次只能带一样东西并且运送每件物品过后必须返回邮局。求送完这 n − 1 n-1 n−1 样东西并且最终回到邮局最少需要的时间。
输入格式
第一行包括两个整数 n n n 和 m m m表示城市的节点数量和道路数量。
第二行到第 ( m 1 ) (m1) (m1) 行每行三个整数 u , v , w u,v,w u,v,w表示从 u u u 到 v v v 有一条通过时间为 w w 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 % 30\% 30% 的数据 1 ≤ n ≤ 200 1 \leq n \leq 200 1≤n≤200。
对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 1 0 3 1 \leq n \leq 10^3 1≤n≤103 1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1≤m≤105 1 ≤ u , v ≤ n 1\leq u,v \leq n 1≤u,v≤n 1 ≤ w ≤ 1 0 4 1 \leq w \leq 10^4 1≤w≤104输入保证任意两点都能互相到达。
#includebits/stdc.h
using namespace std;
#define pii pairint,int
#define il inline
#define re register
const int MAXN1e5;
int u[MAXN],v[MAXN],w[MAXN];
int dis[MAXN];
int n,m;//反向建边
il void over()
{for(int i1;im;i)swap(u[i],v[i]);return;
}
////Bellman Ford
il void Ford()
{memset(dis,0x3f3f3f,sizeof(dis));//初始化 dis[1]0;for(int k1;kn;k)for(int i1;im;i)dis[v[i]]min(dis[v[i]],dis[u[i]]w[i]);return;
}
// int main()
{int ans0;cinnm;for(int i1;im;i)cinu[i]v[i]w[i];Ford();for(int i1;in;i) ansdis[i];//从一到多
// for (int i1;in;i) coutdis[i] ;over();//反向建图 Ford();//再跑一遍 for(int i1;in;i) ansdis[i];//从多到一 coutans;return 0;
}ps:
单源最短路问题用bellman-ford解决这是一道bellman-ford模板题
bellman-ford: 设 f ( k , i ) 为经过 k 条边的情况下 f − k 的最短路 设f(k,i)为经过k条边的情况下f-k的最短路 设f(k,i)为经过k条边的情况下f−k的最短路 若存在有向边 ( u , v , w ) 则用 f ( k , u ) w 更新 f ( k 1 , v ) 若存在有向边(u,v,w)则用f(k,u)w更新f(k1,v) 若存在有向边(u,v,w)则用f(k,u)w更新f(k1,v) 根据题目要求因为要来回跑所以反向建图再跑一遍bellman-ford即可
end
