题解 | #【模板】单源最短路2#

【模板】单源最短路2

https://www.nowcoder.com/practice/7c1740c3d4ba4b3486df4847ee6e8fc7

首先看题目，发现是单源最短路，脑子里面蹦出来几个可行的算法~~~

1.dijstra
完美做出，但条件是不能有负权边，堆优化以后复杂度是O(mlogn)。
2.bellman-ford
主要用于有负权边的情况，理论复杂度是O(nm)，但队列优化以后往往远小于这个复杂度。
3.floyd
多源最短路算法，这里也拿过来一块学了，复杂度是O(n3)O(n3)，所以不应该用多元最短路算法floyd去求高效率的单源最短路。
再看题目描述

给你一个无向图，图中包含 5000 个点 m 个边，任意两个点之间的距离是 w ，无重边或自环。请求出1号点到n号点的最短距离。

注意：图中可能存在孤立点，即存在点与任意点都没有边相连

如果1号点不能到达n号点，输出-1.

没有重边那就不用去重，而且不存在自环，咦？自环，莫非，噢噢噢长度还是都大于1的，那应该也不存在负边，所以直接搞吧，就迪杰斯特拉上板子看看

我擦，居然没注意边的数量，看看我以前做的笔记

看来得用领接表的存储方发~~~~

稍微改一下！

哦豁一发过啦~~~

#include<bits/stdc++.h>
using namespace std;
const int maxn=1.5e5;  
int e[maxn],ne[maxn],h[maxn],dis[maxn],idx,w[maxn];
bool vis[maxn];
int n,m;
typedef pair<int ,int >PII;
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}

int  dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    priority_queue<PII,vector<PII>,greater<PII>>mo;
    dis[1]=0;
    mo.push({0,1});
    while(mo.size())
    {
        auto t=mo.top();
        mo.pop();
        int ver=t.second,distance=t.first;
        if(vis[ver]) continue;
        vis[ver]=1;
        for(int i=h[ver];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>w[i]+distance)
            {
                 dis[j]=w[i]+distance;
                 mo.push({dis[j],j});
            }
        }
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    else return dis[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(h,-1,sizeof h);
    int x,y,z,i;
    cin>>n>>m;
    for(i=0;i<m;i++){
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    cout<<dijkstra()<<endl;
}