spfa算法，采用队列，

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

const int N = 5e6 + 10;

int n, m;

int h[N], e[N], ne[N], idx;

int dist[N], w[N];

bool st[N];

void add(int a, int b, int c)

{

    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;

}

int spfa()

{

    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;

    queue<int>q;

    q.push(1);

    st[1] = true;

    while (q.size())

    {

        int t = q.front();

        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i=ne[i])

        {

            int j = e[i];

            if (dist[j] > dist[t] + w[i])

            {

                dist[j] = dist[t] + w[i];

                if (!st[j])

                {

                    q.push(j);

                    st[j] = true;

                }

            }

        }

    }

    if (dist[n] == 0x3f3f3f3f)

        return -1;

    else

        return dist[n];

}

int main()

{

    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);

    for(int i=0;i<m;i++)

    {

        int a, b, w;

        scanf("%d%d%d", &a, &b, &w);

        add(a, b, w);

        add(b, a, w);

    }

    int t = spfa();

    printf("%d\n", t);

    return 0;

}