P1629 邮递员送信网页链接P1629 邮递员送信题目描述有一个邮递员要送东西邮局在节点1 11。他总共要送n − 1 n-1n−1样东西其目的地分别是节点2 22到节点n nn。由于这个城市的交通比较繁忙因此所有的道路都是单行的共有m mm条道路。这个邮递员每次只能带一样东西并且运送每件物品过后必须返回邮局。求送完这n − 1 n-1n−1样东西并且最终回到邮局最少需要的时间。输入格式第一行包括两个整数n nn和m mm表示城市的节点数量和道路数量。第二行到第( m 1 ) (m1)(m1)行每行三个整数u , v , w u,v,wu,v,w表示从u uu到v vv有一条通过时间为w ww的道路。输出格式输出仅一行包含一个整数为最少需要的时间。输入输出样例 #1输入 #15 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输出 #183说明/提示对于30 % 30\%30%的数据1 ≤ n ≤ 200 1 \leq n \leq 2001≤n≤200。对于100 % 100\%100%的数据1 ≤ n ≤ 10 3 1 \leq n \leq 10^31≤n≤1031 ≤ m ≤ 10 5 1 \leq m \leq 10^51≤m≤1051 ≤ u , v ≤ n 1\leq u,v \leq n1≤u,v≤n1 ≤ w ≤ 10 4 1 \leq w \leq 10^41≤w≤104输入保证任意两点都能互相到达。解题思路本题是有向图上的多源多汇最短路求和问题。邮递员每次从邮局1 11出发将物品送到某个节点i ii后返回1 11。总时间等于所有i 2 ∼ n i2\sim ni2∼n的「1 → i 1 \to i1→i的最短路」与「i → 1 i \to 1i→1的最短路」之和。由于道路是有向的去程和返程的最短路可能不同需要分别计算。1. 问题等价转化去程从1 11到每个i ii的最短距离d i s t 1 [ i ] dist1[i]dist1[i]可通过在正向图上运行单源最短路以1 11为源点求得。返程从每个i ii到1 11的最短距离d i s t 2 [ i ] dist2[i]dist2[i]。若在反向图上运行单源最短路以1 11为源点得到的d i s t 2 [ i ] dist2[i]dist2[i]即为原图中i → 1 i \to 1i→1的最短距离。反向图的构造方法将原图中的每条有向边u → v u \to vu→v变为v → u v \to uv→u边权不变。答案∑ i 2 n ( d i s t 1 [ i ] d i s t 2 [ i ] ) \sum_{i2}^n (dist1[i] dist2[i])∑i2n​(dist1[i]dist2[i])。2. 算法实现两次 Dijkstra建图将节点编号扩大为1 ∼ n 1\sim n1∼n和n 1 ∼ 2 n n1\sim 2nn1∼2n两组。对于每条输入边u → v u \to vu→v权值w ww在正向图中添加边u → v u \to vu→v在反向图中添加边v n → u n vn \to unvn→un反向图的节点编号统一加n nn。第一次 Dijkstra以节点1 11为源点在正向图上求最短路径得到d i s t 1 [ i ] d i s [ i ] dist1[i] dis[i]dist1[i]dis[i]i 2 ∼ n i2\sim ni2∼n。第二次 Dijkstra以节点1 n 1n1n为源点在反向图上求最短路径得到d i s t 2 [ i ] d i s [ i n ] dist2[i] dis[in]dist2[i]dis[in]i 2 ∼ n i2\sim ni2∼n对应原节点i ii。累加答案遍历i 2 ∼ n i2\sim ni2∼n将d i s [ i ] dis[i]dis[i]和d i s [ i n ] dis[in]dis[in]相加累加到总答案。输出输出总答案。3. 复杂度分析时间复杂度两次 Dijkstra每次O ( m log ⁡ n ) O(m \log n)O(mlogn)总O ( m log ⁡ n ) O(m \log n)O(mlogn)。n ≤ 10 3 n \le 10^3n≤103m ≤ 10 5 m \le 10^5m≤105完全可行。空间复杂度邻接表存储2 m 2m2m条边距离数组和堆等O ( n m ) O(nm)O(nm)。总结利用反向图计算所有节点到源点的最短路是处理“多对一”最短路的常用技巧。本题只需分别求出1 11到各节点的最短路和各节点到1 11的最短路求和即可。两次 Dijkstra 独立运行代码结构清晰。代码简要说明全局数组与建图head[2n]为链式前向星头指针ver, wei, nxt存储边信息。add(u, v, w)添加一条有向边。读入每条边后正向图添加add(u, v, w)反向图添加add(vn, un, w)。Dijkstra 函数传入源点s初始化距离数组dis为极大值。使用优先队列小根堆按距离贪心松弛。主函数第一次dij(1)累加dis[2..n]到答案。第二次dij(1n)累加dis[n2..2n]到答案。输出答案。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll maxn1234,maxm123456;ll inf9000000000000000LL;ll head[maxn1],ver[maxm1],wei[maxm1],nxt[maxm1],tot,n;voidadd(ll u,ll v,ll w){ver[tot]v;wei[tot]w;nxt[tot]head[u];head[u]tot;}structnodeq{ll x;ll dis;nodeq(ll X,ll DIS):x(X),dis(DIS){}booloperator(constnodeqo)const{returndiso.dis;}};priority_queuenodeq,vectornodeq,greaternodeqpq;ll dis[maxn1];voiddij(ll s){for(ll i1;in1;i)dis[i]inf;dis[s]0;pq.push(nodeq(s,0));while(!pq.empty()){nodeq curpq.top();pq.pop();if(dis[cur.x]cur.dis)continue;for(ll ihead[cur.x];~i;inxt[i]){if(dis[ver[i]]cur.diswei[i]){dis[ver[i]]cur.diswei[i];pq.push(nodeq(ver[i],dis[ver[i]]));}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(head,-1,sizeof(head));ll m,u,v,w;ll ans0;scanf(%lld%lld,n,m);for(ll i1;im;i){scanf(%lld%lld%lld,u,v,w);add(u,v,w);add(vn,un,w);}dij(1);for(ll i2;in;i)ansdis[i];dij(1n);for(ll i2n;in1;i)ansdis[i];printf(%lld\n,ans);return0;}