Dijkstra 堆优化

回顾

迪杰斯特拉-算法回顾 1. 准备工作：设置辅助数组 Dist，其中每个分量 Dist[k] 表示：当前所求得的从源点到其余各顶点k的最短路径。 2. 在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。 3. 修改其它各顶点的 Dist[k] 值。 4. 选出下一条最短路，回到步骤 3，直到求出所有最短路。

堆优化

dist最小值使用priority_queue维护 邻接表：空间+时间优化 O(ElogE)E是边数 原因在于堆不容易删去指定节点 代码

#include<bits/stdc++.h>
#define INF 2147483647
using namespace std;
int n,m,s;
int cnt,head[100005]; //从Dij函数猜测需要的初始化值
int dist[100005],vis[100005];
struct Edge{
    int to,dis,next; 
}edge[200005];
void Add_edge(int from,int to,int w)
{
    edge[++cnt].to=to;
    edge[cnt].dis=w;
    edge[cnt].next=head[from];
    head[from]=cnt;
}
struct node{
    int id,dis;
    bool operator<(const node &a)const{ return a.dis<dis; }
};
priority_queue<node> q;
q.push(node{s,0}); //默认构造函数
for(int i=1;i<=n;i++) dist[i]=INF;
dist[s]=0;
while(!q.empty())
{
    node a=q.top(); q.pop();
    int now=a.id;
    if(vis[now]) continue;
    vis[now]=1;
    for(int i=head[now];i;i=edge[i].next)
    {
        int j=edge[i].to;
        if(dist[now]+edge[i].dis<dist[j])
        {
            dist[j]=dist[now]+edge[i].dis;
            q.push(node{j,dist[j]});
        }
    }
}

int main(){
	...;
}

例题 luogu P4779

最短路 代码

题目描述 Problem Description 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input 输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。

Output 对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间 输入样例 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 输出样例 3 2

解题代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f

struct {
    int to;
    int next;
    int dis;
}edge[20010];
int head[110];
bool vis[110];
int cnt=0;

int n,m;
struct node {
    int index;
    ll dist;
    friend bool operator <(node p1,node p2){
        return p1.dist>p2.dist;
    }
};
ll dist[110];
priority_queue<node> q;

void addedge(int from,int to,int dis){
    edge[++cnt].to=to;
    edge[cnt].dis=dis;
    edge[cnt].next=head[from];
    head[from]=cnt;
    return ;
}

ll dij(int s,int t){
    while(!q.empty()){
        q.pop();
    }
    for(int i=0;i<=n;i++){
        dist[i]=inf;
    }
    memset(vis,0,sizeof(vis));
    // q.push(node{2,3});
    // q.push(node{3,4});
    // cout<<q.top().dist<<endl;
    dist[s]=0;
    q.push(node{s,0});
    while(!q.empty()){
        node now=q.top();
        q.pop();
        int i=now.index;
        // cout<<i<<endl;
        if(i==t){
            return dist[t];
        }
        if(vis[i]){
            continue;
        }
        vis[i]=true;
        for(int k=head[i]; k!=0; k=edge[k].next){
            int to=edge[k].to;
            int dis=edge[k].dis;
            // cout<<dist[i]<<" "<<dist[to]<<" "<<dis<<endl;
            if(dist[i]+dis<dist[to]){
                dist[to]=dist[i]+dis;
                q.push(node{to,dist[to]});
            }
        }
    }
    return -1;
}

int main(){
    while(scanf("%d%d",&n,&m),n && m){
        memset(head,0,sizeof(head));
        cnt=0;

        for(int i=1;i<=m; i++){
            int from,to,dis;
            scanf("%d%d%d",&from,&to,&dis);
            addedge(from,to,dis);
            addedge(to,from,dis);
        }
        printf("%lld\n",dij(1,n));
    }
    return 0;
}