上午把P1629 邮递员写了一封信。我在哔哩哔哩看了两种小生成路的动态解释。

P1629 邮递员送信

题目描述

有一个邮递员东西，邮局在节点 11.他总共要送 n-1n?1 样品的目的地是节点 22 到节点 nn。由于城市交通繁忙，所有道路都是单行的，共有的 mm 一条路。邮递员每次只能带一件东西，而且运送每件物品后必须返回邮局。求送完这 n-1n?1 样东西并且最后回邮局至少需要时间。

输入格式

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

第二行到第 (m 1)(m 1) 行，每行三个整数，u,v,wu,v,w，表示从 uu 到 vv 通过时间有一个 ww 的道路。

输出格式

输出只有一行，包括一个整数，至少需要时间。

输入输出样例

输入 #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\0% 的数据，1 \leq n \leq 2001≤n≤200。

对于 100\0% 的数据，1 \leq n \leq 10^31≤n≤103，1 \leq m \leq 10^51≤m≤105，1\leq u,v \leq n1≤u,v≤n，1 \leq w \leq 10^41≤w≤104，输入保证任意两点都能互相到达。

想法：邮递员每次都会带一封电子邮件到相应的点，这是迪杰斯特拉找到的最小点，但这条路不一定是最短的。所以反向使用它dij。

代码实现：

#include using namespace std; int n,m; int dvis[1000000]; int fvis[1000000]; int dlow[1000000]; int flow[1000000]; int maxm=1e9; struct edge{  int to;  int v;  int next; }dmp[100000],fmp[100000]; int dhead[1000000]; int fhead[1000000]; struct node {  int dis;  int v;  bool operator <(const node &x) const  {   return x.vq;  for(int i=1;i<=n;i  )  dlow[i]=maxm;  dlow[1]=0;  q.push((node){1,0});  while(q.size()!=0)  {   node x=q.top();   q.pop();   int dis=x.dis;   if(dvis[dis]==1)   continue;   dvis[dis]=1;   for(int i=dhead[dis];i!=0;i=dmp[i].next)   {    int t=dmp[i].to;    if(dlow[t]>dlow[dis] dmp[i].v)    {    dlow[t]=dlow[dis] dmp[i].v;         q.push((node){t,dlow[t]});       }   }  } } void fdij() {  for(int i=1;i<=n;i  )  flow[i]=maxm;  flow[1]=0;  priority_queueq;     q.push((node){1,0});     while(q.size()!=0)     {      node x=q.top();      q.pop();      int dis=x.dis;      if(fvis[dis]==1)      continue;      fvis[dis]=1;      for(int i=fhead[dis];i!=0;i=fmp[i].next)      {       int t=fmp[i].to;       if(flow[t]>flow[dis] fmp[i].v)       {        flow[t]=flow[dis] fmp[i].v;        q.push((node){t,flow[t]});    }   }  } } int main() {  cin>>n>>m;  int a,b,v;  for(int i=1;i<=m;i  )  {   cin>>a>>b>>v;   add(a,b,v);  }  dij();  fdij();  int sum=0;  for(int i=2;i<=n;i  )  {   sum=sum dlow[i] flow[i];  }  cout<

4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3

7

#include using namespace std; int n,m; struct node{  int a;//起点   int b;//终点  int v;//距离  }mp[200010]; int father[5001]; bool compare(node a,node b) {  return a.v>n>>m;  for(int i=1;i<=n;i  )  father[i]=i;  int a,b,v;  for(int i=0;i>a>>b>>v;   mp[i].a=a;   mp[i].b=b;   mp[i].v=v;  }  k();  }