题解 | 邮递员送信

这道题好难，首先要知道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;
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⡀⣀⣠⣤⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⡀⢀⣴⣾⣷⣶⣾⣿⣿⣿⣿⣿⣿⣿⣿⣷⣾⣿⣷⣦⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⠿⠛⠛⠉⠉⠉⠉⠉⠉⠛⠻⠿⣿⣿⣿⣿⣿⣶⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⡿⠿⠛⠉⠉⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣀⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⣰⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⣾⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣶⣄⠀⠀⠀⠀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣻⣿⣿⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢹⣿⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣿⠁⠈⢢⡀⠀⠀⠀⢸⡇⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣿⡟⠒⢦⡀⠀⠀⠀
⠀⠀⣠⣤⣤⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡇⠀⠀⠀⠉⢢⣄⠀⠀⢿⠊⠳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣷⡄⠀⢷⠀⠀⠀
⠀⢰⠇⠀⣰⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⡌⣹⠗⠦⣬⣇⠀⠉⢢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⢸⡄⠀⠀
⠀⡟⠀⣼⣯⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣆⢹⡀⠀⠀⠀⠉⠁⠀⠀⢀⣀⡁⠀⠀⠉⠳⢴⡆⠀⠀⠀⠀⠀⠀⢹⣧⠈⡇⠀⠀
⠀⡇⠀⠀⢻⣦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⠻⠉⠛⠂⠀⠀⠀⠀⠀⠀⠻⠿⣿⣿⣿⣶⣦⡀⠛⣇⠀⠀⠀⠀⠀⣈⣿⠀⡇⠀⠀
⢸⡇⠀⠀⢠⣿⣷⣦⣀⡸⣷⣦⣶⡂⠉⠉⠉⢁⣤⣶⡶⠀⠀⠀⣀⣀⡴⠀⠀⠀⠀⠀⠀⠈⠉⠉⠁⠀⡟⢀⣴⣟⣰⣾⣿⣏⣠⠇⠀⠀
⠈⡇⠀⠀⢸⣿⠁⠉⣿⠛⠛⠃⡇⠀⠀⢠⣶⣿⡿⠛⠁⠀⠀⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⢿⠟⠿⢿⡏⠀⠘⣿⡀⠀⠀⠀
⠀⢷⣀⣀⣿⠇⠀⠀⢿⡇⠀⢀⢱⡀⠀⠛⠛⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠀⢸⠇⠀⠀⢹⣿⣄⠀⠀
⠀⠀⣉⣿⡏⠀⠀⠀⠀⠀⠀⢸⣇⣳⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡰⣿⠃⠀⠀⠀⠀⠀⠀⣿⠈⢧⠀
⠀⠘⣿⣿⠁⠀⠀⠀⠀⠀⠀⠘⣿⡛⣶⠀⠀⣠⠔⠒⠛⠒⠦⡀⠀⠀⠀⠀⣠⡤⠶⠤⢤⣀⠀⠀⠀⢀⣏⡄⠀⠀⠀⠀⠀⡀⣿⡆⠈⣧
⣠⡾⠛⣿⣿⣧⠀⠀⠀⠀⢸⣿⠾⢿⡿⠀⣰⠃⠀⠀⠀⠀⠀⢹⡄⠀⠀⡼⠁⠀⠀⠀⠀⠈⠙⣦⠀⢸⣿⡇⣾⣣⡀⠀⢰⣿⣿⣿⣤⠾
⡟⠀⠀⠻⣿⡟⢷⡄⣤⡀⠈⣿⡀⣸⠇⠀⠏⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⡇⢀⡀⠀⠀⠀⠀⢀⡟⠀⠀⠋⣿⣿⣿⡇⣠⣿⠿⠛⢷⡀⠀
⠀⠀⠀⠀⣿⣇⣨⣿⣿⣿⣦⣽⣷⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠁⠀⠀⠃⠀⠙⠢⠤⠤⠴⢾⠀⠀⠀⠀⢸⣷⣿⣿⠟⠁⠀⠀⠈⣧⠀
⠀⠀⠀⠀⠈⠉⠉⠁⠈⠉⠈⢉⣿⡁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⣿⠀
*/