朴素dijkstra

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<set>
#include<cstring>
#include<map>
#include<unordered_map>
#include<queue>

#define x first
#define y second
#define int long long 
#define fast ios::sync_with_stdio(false);cin.tie(0);
#define Endl endl
using namespace std;
const int N=1e6+10;
struct E{
    int v,w;
};
vector<E>g[N];
int st[N],dist[N];
int n,m,sat,en;
void dijkstra(int u)
{
    //st[u]=1;
    dist[u]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
            t=j;
        }

        st[t]=-1;

        for(auto j:g[t])
        {
            int v=j.v,w=j.w;
            if(dist[v]>dist[t]+w)
            dist[v]=dist[t]+w;
        }
    }
}
void solve()
{
    cin>>n>>m>>sat>>en;
    for(int i=1;i<=n;i++)dist[i]=1e9;
    for(int i=0;i<m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }

    dijkstra(sat);

    cout<<dist[en]<<endl;
}    

signed main()
{
    fast;
    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}

堆优化dijkstra

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<set>
#include<cstring>
#include<map>
#include<unordered_map>
#include<queue>

#define x first
#define y second
#define int long long 
#define fast ios::sync_with_stdio(false);cin.tie(0);
#define Endl endl
using namespace std;
const int N=1e6+10;
struct E{
    int v,w;
};
vector<E>g[N];
int st[N],dist[N];
int n,m,sat,en;
void dijkstra(int u)
{
    dist[u]=0;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>heap;
    heap.push({0,u});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();
        int ver=t.y;
        int distance=t.x;
        if(st[ver])continue;
        st[ver]=1;
        for(auto i:g[ver])
        {
            int v=i.v,w=i.w;
            if(dist[v]>distance+w)
            {
                dist[v]=distance+w;
                heap.push({dist[v],v});
            }
        }
    }
}
void solve()
{
    cin>>n>>m>>sat>>en;
    for(int i=1;i<=n;i++)dist[i]=1e9;
    for(int i=0;i<m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }

    dijkstra(sat);

    cout<<dist[en]<<endl;
}    

signed main()
{
    fast;
    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}

spfa

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<set>
#include<cstring>
#include<map>
#include<unordered_map>
#include<queue>

#define x first
#define y second
#define int long long 
#define fast ios::sync_with_stdio(false);cin.tie(0);
#define Endl endl
using namespace std;
const int N=1e6+10;
struct E{
    int v,w;
};
vector<E>g[N];
int st[N],dist[N];
int n,m,sat,en;
void spfa(int u)
{
    dist[u]=0;
    st[u]=1;
    queue<int>q;
    q.push(u);

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        st[t]=0;
        for(auto i:g[t])
        {
            int v=i.v,w=i.w;
            if(dist[v]>dist[t]+w)
            {
                dist[v]=dist[t]+w;
                if(!st[v])
                {
                    st[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
void solve()
{
    cin>>n>>m>>sat>>en;
    for(int i=1;i<=n;i++)dist[i]=1e9;
    for(int i=0;i<m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }

    spfa(sat);

    cout<<dist[en]<<endl;
}    

signed main()
{
    fast;
    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}

floyd

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<set>
#include<cstring>
#include<map>
#include<unordered_map>
#include<queue>

#define x first
#define y second
#define int long long 
#define fast ios::sync_with_stdio(false);cin.tie(0);
#define Endl endl
using namespace std;
const int N=1e2+10;
int g[N][N];
int n,m;
void floyd()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    g[j][k]=min(g[j][i]+g[i][k],g[j][k]);
}
void solve()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++)
    {
        int u,v,c;
        cin>>u>>v>>c;
        g[u][v]=g[v][u]=min(g[u][v],c);

    }
    for(int i=1;i<=n;i++)
    g[i][i]=0;
    floyd();

    int ans=0;
    for(int i=1;i<=n;i++)
    ans=max(g[1][i],ans);

    if(ans==g[1][n+1])
    cout<<-1<<endl;
    else
    cout<<ans<<endl;
}    

signed main()
{
    fast;
    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solve();
    }
    return 0;
}