P1629 邮递员送信

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 ≤ 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\le u,v\le n$， 1 ≤ w ≤ 1 0 4 1 \leq w \leq 10^4 1≤w≤104，输入保证任意两点都能互相到达。

解题思路

• 题意：这题可以抽象成最短路问题，即在一张有向图中，从1号点到其他n-1个点的最短路的和再加上其他n-1个点到1号点最短路的和的值。
• 思路：看这题数据范围，可以用堆优化版的Dijkstra算法，SPFA（Bellman-ford）算法，（虽然有些题SPFA可能会卡，但这题最坏nm复杂度，也没问题），但比较震惊的是这题也可以用Floyd算法（虽然这个时间复杂度比较玄学开个O2优化也可以过）。然后注意到这是一张有向图，而邮递员送完一件东西之后还要返回，也就是说我们从1号点跑出去之后，还要从各个点回到1号点，那我们想，假设从k号点到1号点的最短路是经过k->a->b->1这样一个过程，那么这个过程可以拆解成k->a,a->b,b->1,那么就说明k,a,b,1之间是存在路径的，那么从而1->b,b->a,a->k之间也是有路径的，那么这时候问题其实转化成了反向1号点到k号点的最短路，那么只要再建一个反向图求一下1号点到各个点的最短路然后求个和就行了。
• 注意：建边的时候一定要注意把相应数组开大两倍，以免RE。

代码

• 堆优化版的Dijkstra

#include 
#include 
#include 
#include 
using namespace std;
const int N=2e5+10;//稀疏图
typedef pair<int,int> PII;
int h[N],e[N],ne[N],v[N],idx,n,m,dist[N],ans=0;
bool st[N];
void add(int a,int b,int c){//稀疏图要用邻接表来存，先写add操作函数 e[idx]=b;//第一个插入点的权值是b，表示a可以到bne[idx]=h[a];//idx结点指向头节点指向的结点v[idx]=c;//这两个结点的边权是ch[a]=idx++;//把表头指向的值++ 
}
int dij(int x){memset(dist,0x3f,sizeof(dist));//第一步与稀疏图一样，把所有dist赋值正无穷priority_queue<PII,vector<PII>,greater<PII>>heap;//优先队列的定义小根堆 heap.push({0,x});//等价于将1到1的距离赋值给0，再放入堆内while(heap.size()){//如果堆不空 PII t=heap.top();//把堆顶取出heap.pop();//将堆顶弹出int ver=t.second,distance=t.first;//将堆顶序号赋给ver距离赋给distance if(st[ver]) continue;//如果堆顶已经出现过，就不管st[ver]=1;//没出现过，就开始跟新最短路，先将st变成1for(int i=h[ver];i!=-1;i=ne[i]){//从这个点更新其他点的最短路 int j=e[i];//指的是这条路上的点 if(dist[j]>distance+v[i]){//相当于用1到t的距离去更新//其他点的最短路dist[j]=distance+v[i];heap.push({dist[j],j});//又找到一个点的最短路，将其放入堆 } } } 
}
int main(){cin>>n>>m;memset(h,-1,sizeof(h));//单链表的初始化 ，将表所有头初始化成-1while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c); //建图过程 add(b+n,a+n,c);//加n为了更直观地与上面区分开来 （反向建图） } dij(1);for(int i=2;i<=n;i++) ans+=dist[i];dij(n+1);for(int i=n+2;i<=2*n;i++) ans+=dist[i];//两次dij遍历求和 cout<<ans<<endl; return 0;
} 

• SPFA
  （开始我其实想只建一次图，然后跑n次SPFA，求SPFA(i，1)+SPFA(1，i)），后来发现妥妥 TLE，只有70分，AC代码只跑了2次SPFA。

#include 
#include 
#include 
using namespace std;
const int N=2e5+10;
int idx,e[N],h[N],ne[N],v[N],dist[N],ans=0;
bool st[N];
int n,m;
void add(int a,int b,int c){e[idx]=b;v[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
int spfa(int x){memset(dist,0x3f,sizeof(dist));dist[x]=0;queue<int>q;q.push(x);st[x]=1;while(q.size()){int t=q.front();q.pop();st[t]=0;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+v[i]){dist[j]=dist[t]+v[i];if(!st[j]){q.push(j);st[j]=1;}}}}
}
int main(){cin>>n>>m;memset(h,-1,sizeof(h));while(m--){int a,b,c;cin>>a>>b>>c;add(a,b,c);add(b+n,a+n,c);}spfa(1);for(int i=2;i<=n;i++) ans+=dist[i];spfa(n+1);for(int i=n+1;i<=2*n;i++) ans+=dist[i];cout<<ans<<endl;return 0;
}

• Floyd（模板再加个O2优化也可以过）

#include 
using namespace std;
const int N=1010;
long long d[N][N],n,m,ans=0;
void floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) d[i][j]=0;else d[i][j]=0x3f3f3f3f;}}while(m--){int a,b,c;cin>>a>>b>>c;d[a][b]=min(d[a][b],c*1LL);}floyd();for(int i=2;i<=n;i++){ans+=(d[1][i]+d[i][1]);}cout<<ans<<endl;
}

蒟蒻第一次写题解，如有错误，还望各位大佬多多包涵，多多雅正（QAQ）

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