文件目录

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    long long v; // 目的地
    long long w; // 权重
};
vector<edge> graph[100005]; // 邻接表
long long s, t, d, n, m;
long long dis[100005]; // 记录从起点到达各个顶点的最短距离
bool inq[100005];      // 记录队列中的点
void spfa(int start)
{
    memset(inq, 0, sizeof(inq));
    memset(dis, 0x3f, sizeof(dis));
    queue<int> q; // 正在查询的点集
    q.push(start);
    dis[start] = 0;
    inq[start] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = 0; i < graph[u].size(); i++)
        {
            int v = graph[u][i].v;
            int w = graph[u][i].w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!inq[v])
                {
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    while (m--)
    {
        scanf("%d %d %d", &s, &t, &d);
        if (s == t)
            continue;
        graph[s].push_back({t, d});
    }
    spfa(1);
    cout << dis[n];
    return 0;
}