邮递员送信

这道题好难，首先要知道Dijkstra算法喵~

其实就是最短路径算法喵~

Dijkstra算法的核心思想：贪心+广度优先搜索

想象一下，猫猫（起点）在一个有很多房间（顶点）和走廊（边）的大房子里，每个走廊的长度（权重）都不一样。猫猫想知道自己去每个房间的最短路径，特别是去那个藏着小鱼干的房间（终点）的最短路！Dijkstra算法就是这个聪明的找路方法。

它的核心思想是：从一个起点出发，逐步向外探索，每次都选择当前已知距离最短且尚未确认的房间作为“中转站”，并用这个中转站到起点的距离，去更新它所有邻居房间到起点的可能最短距离。 这个过程会一直持续，直到所有房间的最短距离都被确定下来。

Dijkstra算法的工作步骤喵！

1. 初始化准备喵 ：准备一个 “最短距离记录本” （通常是一个数组），记录从起点猫窝到每个房间的当前最短距离。一开始，只有起点到自己的距离是0，到其他所有房间的距离都是 “无穷大” （表示暂时还不知道路，或者路不通）。准备一个 “待探索房间清单” （通常是一个优先队列/最小堆），里面放着所有还没最终确定最短路径的房间。一开始，这个清单里包含所有房间。（可选）还可以准备一个 “前驱房间记录本” （比如prev数组），用来记录最快到达某个房间之前，是从哪个房间过来的，方便最后回溯整条最短路径。
2. 开始探索循环喵：从 “待探索房间清单” 里，找出那个离起点（猫窝）当前距离最短的房间，我们叫它 “当前房间”。第一次循环时，找到的肯定是起点本身，因为它的距离是0，最小喵！把这个 “当前房间” 标记为 “已确认” （从待探索清单中移出），意味着它的最短距离已经确定，不会再被改变了。非常重要的一步喵！扫描“当前房间”的所有邻居：看看从起点经过“当前房间”再到它的每个邻居，会不会比之前记录的去邻居的路径更短。如果发现了更短的路径，就更新邻居的 “最短距离记录本” ，并把这条新路径的距离和邻居房间放进 “待探索房间清单”。
3. 一直重复上面的循环步骤，直到 “待探索房间清单” 变空（意味着所有房间的最短路径都已确定）或者找到了特定目标房间的最短路径。这时，“最短距离记录本” 里存储的就是从起点猫窝到每个房间的真正最短距离了喵！

最终，它就能可靠地找出从起点到所有其他点的最短路径啦（前提是路径权重不能是负数）！

如果还是很难理解的话可以看一看b站上的视频喵！

接下来说说怎么实现吧！

首先猫猫构建了两个图：

• 正向图 (z)：存储从路口s到路口e的路，用于计算从1号房子（起点）到其他所有路口的最短时间 (to数组)。
• 反向图 (f)：存储的是与原方向相反的路，即从路口e到路口s的路。（注意喵！）在反向图上以1号房子为起点跑最短路径算法，得到的结果back[i]，实际意义上就是从i号房子到达1号房子的最短时间。

这样，只需要跑两次Dijkstra算法，就可以分别得到 to[i]（从1到i的时间）和 back[i]（从i回到1的时间），最后把每个路口的这两个时间加起来就得到总和了喵！

#include <bits/stdc++.h>
using namespace std;

struct lu//路结点
{
    int e;//这条小路通向哪个路口呀
    int v;//走完这条小路要花多少时间喵
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin >> n >> m;
    vector<int> to(n+1,1e9);//到达i所需要的时间
    vector<int> back(n+1,1e9);//从i返回所需要的时间
    vector<vector<lu>> z(n+1);//正向图
    vector<vector<lu>> f(n+1);//反向图

    for(int i=0;i<m;i++)
    {
        int s,e,v;cin >> s >> e >> v;//起点，终点，所花时间
        z[s].push_back({e,v});
        f[e].push_back({s,v});
    }

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    //<所花时间，起点>
    //计算从邮局出发去各路口的最短时间喵！
    pq.push({0,1});//从邮局开始探索喵，所花时间当然是0啦
    while(!pq.empty())
    {
        auto [time,start]=pq.top();//到达start所花时间time
        pq.pop();
        //如果发现更近的路已经找到了，就跳过这个需要花更长时间才能到的路口喵
        if(time>to[start]) continue;
        // 检查从这个路口能去的所有相邻路口喵
        for(auto& i:z[start])
        {
            int new_time =i.v+time;
            if(new_time<to[i.e])//发现更近的路啦，更新地图~
            {
                to[i.e]=new_time;
                pq.push({new_time,i.e});
            }
        }
    }
    //计算从各路口出发去各路口的最短时间喵！
    //以下和上方除了变量名一摸一样
    pq.push({0,1});
    while(!pq.empty())
    {
        auto [time,start]=pq.top();
        pq.pop();
        if(time>back[start]) continue;
        for(auto& i:f[start])
        {
            int new_time =i.v+time;
            if(new_time<back[i.e])
            {
                back[i.e]=new_time;
                pq.push({new_time,i.e});
            }
        }
    }
    //输出结果
    int ans=0;
    for(int i=2;i<=n;i++) ans+=to[i]+back[i];
    cout << ans;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/

#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define int long long
const int INF=1e18;
void solve(){
    int n,m;cin>>n>>m;
    vector<vector<int>> val(n+1,vector<int>(n+1,INF)),val2(n+1,vector<int>(n+1,INF));
    vector<int> d(n+1,INF),d2(n+1,INF);
    vector<bool> vis(n+1,false),vis2(n+1,false);
    d[1]=d2[1]=0;
    while(m--){
        int u,v,w;cin>>u>>v>>w;
        val[u][v]=w;
        val2[v][u]=w;
    }
    for(int i=1;i<=n;i++){
        int u=-1,minn=INF;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&d[j]<minn){
                u=j;
                minn=d[j];
            }
        }
        if(u==-1) break;
        vis[u]=true;
        for(int k=1;k<=n;k++){
            if(!vis[k]&&val[u][k]<INF){
                d[k]=min(d[k],d[u]+val[u][k]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        int u=-1,minn=INF;
        for(int j=1;j<=n;j++){
            if(!vis2[j]&&d2[j]<minn){
                u=j;
                minn=d2[j];
            }
        }
        if(u==-1) break;
        vis2[u]=true;
        for(int k=1;k<=n;k++){
            if(!vis2[k]&&val2[u][k]<INF){
                d2[k]=min(d2[k],d2[u]+val2[u][k]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=d[i]+d2[i];
    }
    cout<<ans;
} 
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}

代码设计与技巧解析：
本文使用了ai辅助，旨在更好的帮助大家理解一些技巧

邮递员送信_牛客题霸_牛客网

以这一题为例，需要对节点 1 求 两次 dijkstra，怎么使得代码写的简洁？
ac 代码如下，我们来一一解析：

void solve()
{
    int n(q_), m(q_);
    using ED = array<int, 2>;
    using GRAPH = vector<vector<ED>>;

    GRAPH tr(n + 1);
    GRAPH rtr(n + 1);
    ffp(i, 1, m)
    {
        int u(q_), v(q_), w(q_);
        tr[u].push_back({ w,v });//tr是树边，本人的习惯
        rtr[v].push_back({ w,u });//rtr是反图
    }

    auto dij = [&](int st, GRAPH& gp)->ll
        {
            priority_queue<ED, vector<ED>, greater<ED>>dui;
            vector<int>dis(n + 1, iINF); dis[st] = 0;

            dui.push({ 0,st });
            while (dui.size())
            {
                auto [w, now] = dui.top();
                dui.pop();
                if (dis[now] < w)continue;
                for (auto [nxtw, nxt] : gp[now])
                {
                    if (nxtw + dis[now] >= dis[nxt])continue;
                    dis[nxt] = nxtw + dis[now];
                    dui.push({ nxtw + dis[now],nxt });
                }
            }
            return accumulate(dis.begin() + 1, dis.end(), 0ll);
        };
    cout << dij(1, tr) + dij(1, rtr) << endl;
    return;
}

【初始化与快读】 首先，我们使用 n(q_), m(q_) 对变量进行初始化。这里的 q_ 是封装好的快读对象（Fast I/O），用于高效读取整数。值得一提的是，n(q_) 使用的是直接初始化（Direct Initialization），而我们常见的 n = q_ 属于复制初始化（Copy Initialization）。虽然在基础类型上二者生成的汇编指令并无差异，但直接初始化更具 Modern C++ 的风格。

【类型别名优化】 为了提升代码的可读性与编写效率，我们使用 using ED = array<int, 2> 为边的存储结构定义别名，同理定义了 GRAPH。这样不仅减少了冗余代码，也便于后续维护。

【存图细节】 在读入边权并建图时，有一个关键细节：tr[u].push_back({ w, v })。请注意，我们将 权值 w 放在了 array 的首位。 这是为了配合后续的 priority_queue。由于 STL 的容器默认按字典序比较（即先比较第一个元素），将权值置于首位，可以直接利用默认的比较规则实现“按权值排序”，无需额外编写比较函数。

【Dijkstra 的封装】 我们使用 Lambda 表达式封装了 Dijkstra 算法。在传参时，图结构 GRAPH 必须使用引用传递（建议为 const 引用），以避免在函数调用时发生巨大的内存拷贝开销，防止 TLE（超时）。

【累加器的陷阱】 计算最终结果时，我使用了 <numeric> 库中的 accumulate 函数。这里潜藏着一个常见的溢出陷阱：accumulate 的第三个参数决定了累加过程的数据类型。 如果传入 0，编译器会将其推导为 int 类型进行累加，这在处理大数时会导致溢出。因此，必须显式传入 0ll（即 long long 类型的 0），以确保计算过程使用长整型。

【I/O 细节】 最后，输出时使用 \n 替代 endl。endl 会强制刷新缓冲区，在大规模输出场景下可能导致显著的性能损耗。