（ 图论专题 ）【 最短路 】

dijkstra的堆优化（最简版本）

先了解不用堆优化的dijkstra：https://blog.csdn.net/weixin_43828245/article/details/90722389
推荐视频讲解（代码是Python写的，重点听思路）：https://www.bilibili.com/video/av25829980
了解c++优先队列：https://blog.csdn.net/weixin_43828245/article/details/90742490
 

#include <iostream>
#include <queue>
#include <cstring>

#define inf 0x3f3f3f

using namespace std;

typedef struct node {
    int v,date;
} ty;

bool operator < ( const ty &a, const ty &b ) // 自定义优先队列规则，先pop出小的来
{
    return a.date>b.date;  // 这里和sort相反，a>b是先pop出小的
}

int a[2002][2002];
int via[2002];  // 判断是否已经pop出来了
int dis[2002];  // 存放距离
int i,j,n,m;
ty t,d;

void dijkstra( int v0 )
{
    priority_queue <ty> Q;  // 自定义的优先队列
    memset(dis,inf,sizeof(dis));  // 初始化dis为inf，避免和v0相连的点不能进入队列
    dis[v0] = 0;
    t.v = v0;
    t.date = 0;
    Q.push(t); // 先将顶点入队

    while ( !Q.empty() ) {
        if ( via[Q.top().v]==1 ) {  // 如果队列的点已经弹出过了，那么舍弃这个点
            Q.pop();
            continue ;
        }
        t = Q.top();
        Q.pop();
        int u = t.v;
        via[u] = 1;
        dis[u] = t.date; // 对于弹出来的点，就是已经做好了的点

        for ( i=1; i<=n; i++ ) {
            if ( via[i]==0 && a[u][i]<inf && dis[i]>dis[u]+a[u][i] ) {
                dis[i] = dis[u] + a[u][i]; // 更新最短路，并存入队列
                d.v = i;
                d.date = dis[i];
                Q.push(d);
            }
        }
    }
    cout << dis[n] << endl;
}

int main()
{
    cin >> m >> n;
    memset(a,inf,sizeof(a));
    memset(via,0,sizeof(via));
    for ( i=1; i<=n; i++ ) {
        a[i][i] = 0;
    }
    for ( i=1; i<=m; i++ ) {
        int x,y,z;
        cin >> x >> y >> z;
        if ( a[x][y]>z ) {
            a[x][y] = a[y][x] = z;
        }
    }

    dijkstra(1);

    return 0;
}

前向星写的dijkstra

此代码用于稀疏图，或者节点数很多二维数组存不下。在稠密图中可以继续使用邻接矩阵。

#include <iostream>
#include <stdio.h>
#include <queue>
#include <cstring>
#define inf 0x3f3f3f

using namespace std;

typedef struct node { // 定义优先队列
    int v,date;
} ty;

bool operator < ( const ty &a, const ty &b )  // 定义优先队列
{
    return a.date>b.date;
}

struct edge {      // 存邻接表的边
    int to,w,next;
} a[100005];

int head[105];
int dis[105];
int via[105];
int cnt;
int n,m;
ty t,d;

void dijkstra( int v0 ) // 堆优化的dijkstra + 邻接表
{
    priority_queue <ty> Q;
    memset(dis,inf,sizeof(dis));
    dis[v0] = 0;
    t.v = v0;
    t.date = 0;
    Q.push(t);

    while ( !Q.empty() ) {
        if ( via[Q.top().v]==1 ) {
            Q.pop();
            continue ;
        }
        t = Q.top();
        Q.pop();
        int u = t.v;
        dis[u] = t.date;
        via[u] = 1;

        for ( int i=head[u]; i!=-1; i=a[i].next ) {   // 这块代码容易出错，好好看
            int j = a[i].to;                        // 通过邻接表直接找相邻的点
            if ( via[j]==0 && dis[j]>dis[u]+a[i].w ) {
                dis[j] = dis[u]+a[i].w;
                d.v = j;
                d.date = dis[j];
                Q.push(d);
            }
        }
    }

    cout << dis[n] << endl;
}

int main()
{
    while ( cin >> n >> m ) {
        cnt = 0;
        memset(head,-1,sizeof(head));
        memset(via,0,sizeof(via));
        for ( int i=0; i<m; i++ ) {
            int x,y,z;
            scanf("%d %d %d",&x,&y,&z);
            a[cnt].to = y;             // 无向图
            a[cnt].w = z;
            a[cnt].next = head[x];
            head[x] = cnt++;

            a[cnt].to = x;             // 正反存两次
            a[cnt].w = z;
            a[cnt].next = head[y];
            head[y] = cnt ++;
        }
        dijkstra(1);
    }

    return 0;
}

 

F - Wormholes（SPFA+邻接矩阵）

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f
 
using namespace std;
 
int a[505][505];
int dis[505*505];
int via[505];
int n,m,mm,t;
 
void init() // 初始化
{
    memset(a,inf,sizeof(a));
    memset(dis,inf,sizeof(dis));
    memset(via,0,sizeof(via));
    for ( int i=1; i<=n; i++ ) {
        a[i][i] = 0;
    }
}
 
int spfa( int node )
{
    queue <int> Q;
    dis[node] = 0;
    via[node] = 1;
    int cnt = 0;
    Q.push(node); // 把根节点push进去 
    Q.push(cnt);  // 紧跟着一个cnt
    while ( !Q.empty() ) {
        int u = Q.front();// pop要两个一起
        Q.pop();
        cnt = Q.front();  // 第一个是节点，第二个是松弛的次数cnt
        Q.pop();
        via[u] = 0; // 取消标记，容易遗漏
        if ( cnt>n ) { // 如果松弛次数大于n，肯定存在负权回路
            return 0;
        }
        for ( int i=1; i<=n; i++ ) {
            if ( dis[i]>dis[u]+a[u][i] ) { // 更新最短路
                dis[i] = dis[u]+a[u][i];
                if ( via[i]==0 ) { // 如果更新完没标记，push进来
                    via[i] = 1;
                    Q.push(i);
                    Q.push(cnt+1);
                }
            }
        }
    }
    return 1;
}
 
int main()
{
    int listt,i,j,x,y,z;
    cin >> listt;
    while ( listt-- ) {
        cin >> n >> m >> mm;
        init();
        for ( i=0; i<m; i++ ) {
            cin >> x >> y >> z;
            if ( a[x][y]>z ) {
                a[x][y] = a[y][x] = z;
            }
        }
        for ( i=0; i<mm; i++ ) {
            cin >> x >> y >> z;
            if ( a[x][y]>-z ) {
                a[x][y] = -z;
            }
        }
        if ( spfa(1)==0 ) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
 
    return 0;
}

F - Wormholes（SPFA+邻接表）

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f
 
using namespace std;
 
const int maxn = 1e5+10;
int head[maxn];
int dis[maxn];
int via[maxn];
int cnt,n,m,mm;
 
struct node {
    int to,w,next;
} e[maxn];
 
void addage( int u, int v, int w )
{
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
 
int spfa( int node )
{
    memset(via,0,sizeof(via));
    memset(dis,inf,sizeof(dis));
    queue <int> Q;
    dis[node] = 0; via[node] = 1;
    int tot = 0;
    Q.push(node);// 把根节点push进去 
    Q.push(tot);// 紧跟着一个tot
    while ( !Q.empty() ) {
        int u = Q.front(); Q.pop();// pop要两个一起
        tot = Q.front(); Q.pop();
        via[u] = 0;    // 取消标记，这个容易遗漏，（进队列标记为1，出队列取消标记）
        if ( tot>n ) { // 如果松弛次数大于n，肯定存在负权回路
            return 0;
        }
        for ( int i=head[u]; i!=-1; i=e[i].next ) {
            int y = e[i].to, w = e[i].w;
            if (  dis[y]>dis[u]+w ) {
                dis[y] = dis[u] + w;  // 直接更新最短路，没有其他条件
                if ( via[y]==0 ) { // 更新完了，如果没标记再push这个点进去
                    via[y] = 1;
                    Q.push(y);
                    Q.push(tot+1);                    
                }
            }
        }
    }
    return 1;
}
 
int main()
{
    int listt,i,j,x,y,z;
    cin >> listt;
    while ( listt-- ) {
        cin >> n >> m >> mm;
        memset(head,-1,sizeof(head));
        cnt = 0;
        for ( i=0; i<m; i++ ) {
            cin >> x >> y >> z;
            addage(x,y,z);
            addage(y,x,z);
        }
        for ( i=0; i<mm; i++ ) {
            cin >> x >> y >> z;
            addage(x,y,-z);
        }
        if ( spfa(1)==0 ) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
 
    return 0;
}