最近好虚啊，还是复习一下最经典的最短路吧
floyd太简单就不写了
qwq
写个堆优化dijkstra好了

堆优化dijkstra算法 O(m + nlogn）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define pair pair<int,int>
using namespace std;
struct edg{
    int to,next,v;
}e[12410];
int head[2510],size,f[2510];
const int inf=1000000000;
int t,c,n,m,x,y,z;
priority_queue<pair,vector<pair>,greater<pair> > q;
bool vis[2510];
void add(int x,int y,int z)
{
    size++;
    e[size].to=y;
    e[size].next=head[x];
    e[size].v=z;
    head[x]=size;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&t,&c);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    for (int i=1;i<=n;i++) f[i]=inf;
    f[t]=0;
    q.push(make_pair(0,t));
    while (!q.empty())
    {
        int k=q.top().second;
        q.pop();
        if (!vis[k])
        {
            vis[k]=1;
            for (int i=head[k];i;i=e[i].next)
            {
                int j=e[i].to;
                if (f[j]>f[k]+e[i].v)
                    f[j]=f[k]+e[i].v,q.push(make_pair(f[j],j));
            }
        }
    }
    printf("%d",f[c]);
}