网站建设客户去哪找,qq互联 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输入保证任意两点都能互相到达。 F l o y d Floyd Floyd 逃课做法要开O2
直接套 F l o y d Floyd Floyd
最后的结果是每个点到 1 节点的距离与 1 到每个点的距离之和注意存储初始距离时保留最短的一条否则会WA F l o y d Floyd Floyd做法代码
#includebits/stdc.h
using namespace std;
const int N1e3111;
int n,m,ans0;
int dis[N][N];
int main(){cinnm;memset(dis,0x3f,sizeof(dis));for(int i1;im;i){int u,v,w;cinuvw;dis[u][v]min(dis[u][v],w);//dis[u][v]w;}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}}}for(int i2;in;i){ansdis[i][1]dis[1][i];}coutansendl;return 0;
}d i j k s t r a dijkstra dijkstra堆优化
从 1 1 1 跑到其他 2 n 2~n 2 n 节点需要跑一遍 d i j k s t r a dijkstra dijkstra
返回 1 1 1节点也需要跑一遍 d i j k s t r a dijkstra dijkstra
因此我们在 u n un un 与 v n vn vn 建一个反图方便反跑
需要堆优化
答案累加 2 2 2累加到 n n n反跑后从 2 n 2n 2n 累加到 n ∗ 2 n*2 n∗2即可
AC CODE
#includebits/stdc.h
using namespace std;
const int N1e449999;
int n,m,ans0;
int dis[N];
vectorpairint,int a[N];
bool vis[N];
void dijkstra(int s){priority_queuepairint,int,vectorpairint,int ,greaterpairint,int q;memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]0;q.push({0,s});while(!q.empty()){pairint,int tmpq.top();q.pop();int xtmp.second;int ytmp.first;if(dis[x]tmp.first)continue;if(vis[x]1)continue;vis[x]1;for(int i0;ia[x].size();i){if(dis[a[x][i].first]ya[x][i].second){dis[a[x][i].first]ya[x][i].second;q.push({dis[a[x][i].first],a[x][i].first});}}}
}
int main(){cinnm;for(int i1;im;i){int u,v,w;cinuvw;a[u].emplace_back(make_pair(v,w));a[vn].emplace_back(make_pair(un,w));}dijkstra(1);for(int i2;in;i){ansdis[i];}dijkstra(1n);for(int i2n;in*2;i){ansdis[i];}coutansendl;return 0;
}附封面碧蓝档案
