Dijkstra

Dijkstra：

单源最短路

最基本的复杂度为O(n^2)， 使用优先队列+邻接表，可优化至O(nlogn)

优化后的整体思路不变     （小菜鸡码了好多个代码啊哈哈哈哈

/*
    O(eloge)堆优化dj算法，在n的数量级>=1e5时必须采用这种堆优化+邻接表方式 
*/
struct node{
    int p, w;
    node(int a, int b):p(a), w(b){}
    bool operator< (const node& b) const
    {
        return w > b.w;
    }
};
vector<node> g[N];
priority_queue<node> sup;
void dijkstra(int start)
{
    memset(dis, 0x3f, sizeof(dis));
    dis[start] = 0; pre[start] = start;
    sup.push(node(start, 0));
    while (!sup.empty())
    {
        node front = sup.top();
        sup.pop();  int tempv = front.p;
        if (visit[tempv]) continue;
        visit[tempv] = true;
        for (int i = 0; i < g[tempv].size(); i++)
        {
            int p = g[tempv][i].p;
            if (!visit[p] && dis[tempv]+g[tempv][i].w < dis[p])
            {
                dis[p] = dis[tempv]+g[tempv][i].w;
                pre[p] = tempv;
                sup.push(node(p, dis[p]));
            }
        }
    }
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
const int maxn=100005;
struct node ///优先队列， 在距离相同时选最小花费
{
    int u,v,w,dis;
    node(int _v=0,int _w=0,int _dis=0):v(_v),w(_w),dis(_dis){}
    bool operator <(const node &r)const
    {
        if(dis!=r.dis)
            return dis>r.dis;
        else
            return w>r.w;
    }
};
vector<node> vec[maxn];///存边
int vis[maxn];
int dis[maxn];///存最短路径
int pre[maxn];///存父节点
const int inf=0x3f3f3f3f;
int n,m,c;
void dij()
{
    int load=0;///记录在最短路径的情况下，边权和
    for(int i=1;i<=n;i++)
    {
        pre[i]=i;
        vis[i]=0;
        dis[i]=inf;
    }
    priority_queue<node> q;
    dis[1]=0;
    q.push(node(1,0,0));
    node tmp;
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        int u=tmp.v;
        if(vis[u])
            continue;
        load+=tmp.w;
        vis[u]=1;
        for(int i=0;i<vec[u].size();i++)
        {
 
            int v=vec[u][i].v;
            int cost=vec[u][i].w;
            if(!vis[v]&&dis[v]>=dis[u]+cost)
            {
                pre[v]=tmp.v;
                dis[v]=dis[u]+cost;
                q.push(node(  v,cost,dis[v]));
            }
        }
    }
    cout << "各点父节点： " << endl; 
    for(int i=1;i<=n;i++)
        printf("%d ",pre[i]);
    printf("
%d
",load);
    cout << "源点到各点的最短路权值：" << endl;
    for(int i=1;i<=n;i++)
        printf("%d ",dis[i]);
    printf("
");
}
int main()
{
 
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            vec[i].clear();
        for(int i=1;i<=m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            vec[u].push_back(node(v,w,0));
            vec[v].push_back(node(u,w,0));
        }
        dij();
 
 
}