P1342 请柬【洛谷算法习题】
P1342 请柬
网页链接
P1342 请柬
题目背景
在电视时代，没有多少人观看戏剧表演。Malidinesia 古董喜剧演员意识到这一事实，他们想宣传剧院，尤其是古色古香的喜剧片。
题目描述
他们已经打印了请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天，邀请人们参与。
这里的公交系统是非常特殊的：共有n nn个站点和m mm个线路，所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。
学生每天早上从总部所在的1 11号站点出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候，所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。
输入格式
输入的第一行是两个整数，代表站点个数n nn和线路条数m mm。
第2 22到第( m + 1 ) (m + 1)(m+1)行，每行三个整数u , v , w u, v, wu,v,w，代表存在一条从u uu出发到达v vv的线路，费用为w ww。
输出格式
输出一行一个整数，表示最小费用。
输入输出样例 #1
输入 #1
4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50输出 #1
210说明/提示
数据规模与约定
对于100 % 100\%100%的数据，保证：
- 1 ≤ n , m ≤ 10 6 1 \leq n, m \leq 10^61≤n,m≤106。
- 1 ≤ u , v ≤ n 1 \leq u, v \leq n1≤u,v≤n，1 ≤ w ≤ 10 9 1 \leq w \leq 10^91≤w≤109。
- 从1 11出发可以到达所有的站点。
解题思路
本题是有向图双向最短路经典问题，核心通过「反向图」技巧，将多源最短路转化为两次单源最短路求解，适配百万级数据规模。
问题可拆分为两部分：学生从总部（1号站点）到各站点的去程费用，以及从各站点返回总部的返程费用。
- 去程计算：直接在原图上以1号点为起点，运行一次堆优化Dijkstra算法，得到1到所有站点的最短距离，对应每个学生的最小去程费用。
- 返程计算：所有站点到1号点的最短路，等价于将原图所有边反向后，再以1号点为起点的单源最短路。构建反向图后运行一次Dijkstra，即可得到所有站点返回总部的最短距离。
最后将每个站点的去程距离与返程距离相加，累加所有站点的结果，就是总最小费用。算法采用链式前向星存图，搭配堆优化Dijkstra，时间复杂度为O ( m log n ) O(m\log n)O(mlogn)，同时使用快速输入处理百万级数据，完全适配题目约束。
总结
核心逻辑：将往返路程拆分为两次单源最短路，利用反向图技巧把「多点到一点」的最短路转化为「一点到多点」，仅需两次Dijkstra即可求解。
关键操作：构建正向图与反向图、两次堆优化Dijkstra计算最短距离、累加所有站点的往返费用。
效率保障：仅两次最短路运算，对数级复杂度，配合快读与链式前向星存储，高效处理百万级节点与边数。
代码简要说明
- 快读函数：针对百万级输入优化，采用字符级读取方式，避免标准输入的性能瓶颈，保证大数据量下的输入效率。
- Graph结构体：封装链式前向星的边数组、头指针数组，以及Dijkstra算法函数，代码结构清晰，正向图与反向图可复用同一套逻辑。
- 双图构建：
G1存储原图正向边，对应去程计算；G2存储反向边（起点终点互换），对应返程计算。 - 堆优化Dijkstra：通过重载运算符实现小顶堆，每次取出距离最小的节点进行松弛操作，搭配距离数组与访问标记数组，保证正权图下的正确性与运行效率。
- 结果计算：遍历2~n号所有站点，累加每个站点的去程距离与返程距离，最终输出总最小费用。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;llread(){ll w=0;boolf=true;charc=getchar();while(c<'0'||c>'9'){if(c=='-')f=false;c=getchar();}while(c>='0'&&c<='9')w=(w<<1)+(w<<3)+(c^48),c=getchar();returnf?w:~w+1;}constll Nn=1e6+50;ll n,m;ll Ans;structnode{ll id,dis;friendbooloperator<(node n1,node n2){returnn1.dis>n2.dis;}};structGraph{ll to[Nn],val[Nn],nxt[Nn],fir[Nn],tot;ll d[Nn];boolb[Nn];voidAdd(ll x,ll y,ll z){to[++tot]=y;val[tot]=z;nxt[tot]=fir[x];fir[x]=tot;}voiddijkstra(ll S){priority_queue<node>q;memset(d,127/3,sizeof(d));d[S]=0;q.push((node){S,d[S]});while(!q.empty()){ll x=q.top().id;q.pop();if(b[x])continue;b[x]=true;for(ll k=fir[x];k;k=nxt[k]){ll y=to[k],z=val[k];if(d[y]>d[x]+z){d[y]=d[x]+z;q.push((node){y,d[y]});}}}}}G1,G2;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);n=read();m=read();for(ll i=1;i<=m;i++){ll x=read(),y=read(),z=read();G1.Add(x,y,z);G2.Add(y,x,z);}G1.dijkstra(1);G2.dijkstra(1);for(ll i=2;i<=n;i++)Ans+=G1.d[i]+G2.d[i];printf("%lld\n",Ans);return0;}