一：朴素Dijkstra
849. Dijkstra求最短路 I

#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e2+5;
typedef long long ll;
const int mod=1e9+7;
typedef  unsigned long long ull;
//typedef __int128 LL;
const double eps=10e-8;
const double pi=acos(-1.0);
#define between(x,a,b)(a<=x && x<=b)
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> pII;
typedef pair<int,int> pii;
typedef pair<int,ll> piI;
int a[MAXN][MAXN],d[MAXN];
bool v[MAXN];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    memset(a,0x3f,sizeof a);

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[x][y]=min(a[x][y],z);

    }
    for(int i=1;i<=n;i++)a[i][i]=0;
    memset(d,0x3f,sizeof d);
    d[1]=0;
    for(int cnt=1;cnt<=n;cnt++)
    {
        int t=-1;
        for(int i=1;i<=n;i++)
        {
            if(!v[i]&&(t==-1||d[t]>d[i]))t=i;//选出不在最短路中的最小的点
        }
        v[t]=true;//将最小点加入最短路
        for(int i=1;i<=n;i++)d[i]=min(d[i],d[t]+a[t][i]);//更新最小点到其他点的距离
    }
    if(d[n]==0x3f3f3f3f)d[n]=-1;//不能走到目的地点
    printf("%d\n",d[n]);

    return 0;
}

堆优化Dijkstra
850. Dijkstra求最短路 II

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
typedef long long ll;
const int mod=1e9+7;
typedef  unsigned long long ull;
//typedef __int128 LL;
const double eps=10e-8;
const double pi=acos(-1.0);
#define between(x,a,b)(a<=x && x<=b)
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> pII;
typedef pair<int,int> pii;
typedef pair<int,ll> piI;
int d[MAXN];
bool v[MAXN];
vector<pii>a[MAXN];
priority_queue<pii>q;//pair<-dist,i>//从大到小
//priority_queue<pii,vector<pii>,greater<pii>>q; //从小到大

int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#endif
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[x].push_back({y,z});
    }

    memset(d,0x7f,sizeof d);
    d[1]=0;
    q.push({0,1});
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        if(v[x])continue;
        v[x]=true;
        for(auto to:a[x])
        {
            int u=to.first,val=to.second;
            if(d[u]>d[x]+val)
            {
                d[u]=d[x]+val;
                q.push({-d[u],u});
            }
        }
    }
    if(d[n]==0x7f7f7f7f)d[n]=-1;
    printf("%d\n",d[n]);

    return 0;
}

二：带负权，无负环的最短路
851. spfa求最短路

//SPFA 队列优化的Bellman-ford
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
typedef long long ll;
const int mod=1e9+7;
typedef  unsigned long long ull;
//typedef __int128 LL;
const double eps=10e-8;
const double pi=acos(-1.0);
#define between(x,a,b)(a<=x && x<=b)
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> pII;
typedef pair<int,int> pii;
typedef pair<int,ll> piI;
int d[MAXN];
bool v[MAXN];
vector<pii>a[MAXN];
queue<int>q;
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#endif
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[x].push_back({y,z});
    }

    memset(d,0x7f,sizeof d);
    d[1]=0;
    q.push(1);
    v[1]=true;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        v[x]=false;
        for(auto to:a[x])
        {
            int u=to.first,val=to.second;
            if(d[u]>d[x]+val)
            {
                d[u]=d[x]+val;
                if(!v[u])q.push(u),v[u]=true;
            }
        }
    }
    if(d[n]==0x7f7f7f7f)printf("impossible\n");
    else printf("%d\n",d[n]);

    return 0;
}

//Bellman-ford算法
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
typedef long long ll;
const int mod=1e9+7;
typedef  unsigned long long ull;
//typedef __int128 LL;
const double eps=10e-8;
const double pi=acos(-1.0);
#define between(x,a,b)(a<=x && x<=b)
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<ll,ll> pII;
typedef pair<int,int> pii;
typedef pair<int,ll> piI;
int d[MAXN];
vector<pii>a[MAXN];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("debug.out", "w", stdout);
#endif
    int n,m;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        a[x].push_back({y,z});
    }

    memset(d,0x7f,sizeof d);
    d[1]=0;
    for(int cnt=1;cnt<n;cnt++)
    {
        bool flag=false;
        for(int x=1;x<=n;x++)
        {
            for(auto to:a[x])
            {
                int u=to.first,val=to.second;
                if(d[u]>d[x]+val)
                {
                    d[u]=d[x]+val;
                    flag=true;
                }
            }
        }
        if(!flag)break;
    }
    if(d[n]==0x7f7f7f7f)printf("impossible\n");
    else printf("%d\n",d[n]);

    return 0;
}