华师一附中OI组

标题: P1629 邮递员送信 [打印本页]
作者: admin    时间: 2018-9-18 16:19
标题: P1629 邮递员送信
https://www.luogu.com.cn/problem/P1629
题目描述
有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。

输入输出格式
输入格式：
第一行包括两个整数N和M。

第2到第M+1行，每行三个数字U、V、W，表示从A到B有一条需要W时间的道路。 满足1<=U,V<=N,1<=W<=10000,输入保证任意两点都能互相到达。

【数据规模】

对于30%的数据，有1≤N≤200;

对于100%的数据，有1≤N≤1000,1≤M≤100000。

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

输入输出样例
输入样例#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
作者: admin    时间: 2021-3-21 18:04
这个题做的好的话很考人的建图能力，这题本质的做法就是求1-2,1-3,1-4，***1-n和2-1,3-1,4-1,***n-1等所有最短路径的和。要求这么多的最短经，一个比较简洁的方法就是floyd。我们先用floyd方法做一个试试。

floyd有个模型的理解是矩阵乘法，是我们在用floyd方法时候一般也用领接矩阵来存放图，读入邻接矩阵可不是个简单的事，若是无脑的读入u,v,w然后a(u)(v)=w,极有可能在重复读入的时候出现问题你看样例里面就有两次3 5 6 ，所以应该这样读：
  1. void readmap()
  2. {
  3.         int x,y,z;
  4.         cin>>n>>m;
  5.         /// 没有的边变成inf  ！！！！
  6.         for (int i=1; i<=n; i++)
  7.                 for (int j=1; j<=n; j++)  a[i][j]=inf;
  8.         while (m--)
  9.                 {
  10.                         cin>>x>>y>>z;
  11.                         if (a[x][y]>z)a[x][y]=z;//   这里注意怕 x y有重复
  12.                 }
  13. }
复制代码


读入图后下面的floyd就不难了。
  1. void floyd()
  2. {
  3.         int i,j,k;
  4.         for (i=1; i<=n; i++)
  5.                 for (j=1; j<=n; j++) d[i][j]=a[i][j];
  6.         for (k=1; k<=n; k++)
  7.                 for (i=1; i<=n; i++)
  8.                         for (j=1; j<=n; j++)
  9.                                 if (d[i][j]>d[i][k]+d[k][j])  d[i][j]=d[i][k]+d[k][j];
  10. }
复制代码


交到luogu过了5个点，另外5个TLE，意料之中。因为这里面有了太多的重复计算，那么我们采用单源最短路径如何呢？
我以前写过一个dijistra的最短路径，若是无脑套用，效果不太好。主要原因在



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2