题目描述

Dijkstra求最短路 II

算法1

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>

using namespace std;

typedef pair<int,int> PII;

const int N=2e5+10;

int n;
int m;

int h[N];//邻接表存储稀疏图
int e[N];
int ne[N];
int w[N];
int idx;


bool st[N];
int dis[N];


void add(int a,int b,int c)
{
    e[idx]=b;//e[坐标]=点
    w[idx]=c;//w[坐标]=c

    ne[idx]=h[a];//ne[idx]的下一个坐标是什么坐标
    h[a]=idx;//h[点]=坐标
    idx++;
}

int dijkstra()//堆优化堆Dijkstra
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;

    priority_queue<PII,vector<PII>,greater<>> heap;
    heap.push({0,1});

    while(heap.size())
    {

        auto t=heap.top();
        heap.pop();

        int distance=t.first;
        int v=t.second;

        if(st[v]) continue;

        st[v]=true;

        for(int i=h[v];i!=-1;i=ne[i])
        {
            int j=e[i];//j是点，i是坐标

            if(dis[j] > distance +w[i])
            {
                dis[j]=distance + w[i];
                heap.push({dis[j],j});
            }
        }
    }

    if(dis[n]==0x3f3f3f3f) return -1;

    return dis[n];

}

int  main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);

        add(a,b,c);

    }

    int res=dijkstra();

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

    return 0;
}