点有2500个，边只有6200个，是稀疏图，于是决定学一下spfa

spfa板子题，直接上代码了

心得就是稍微学了一下stl（）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 2550;
const int INF = 9999999;
struct node{
    int v;//终点
    int weight;//权值
};
vector<node>mp[maxn];//下标是起点
int dis[maxn],vis[maxn];//dis是起点到下标的长，vis判断是否入队过
void spfa(int src){
    int q;
    queue<int>Q;
    dis[src]=0;
    vis[src]=1;
    Q.push(src);
    while(!Q.empty()){
        q=Q.front();
        Q.pop();
        vis[q]=0;
        for(int i=0;i<mp[q].size();i++){
            if(dis[q]+mp[q][i].weight<dis[mp[q][i].v]){
                dis[mp[q][i].v]=dis[q]+mp[q][i].weight;
                if(!vis[mp[q][i].v]){
                    Q.push(mp[q][i].v);
                    vis[mp[q][i].v]=1;
                }
            }
        }
    }
    return;
}

int main(){
    int t,c,ts,te;
    cin>>t>>c>>ts>>te;
    for(int i=1;i<=t;i++)
        dis[i]=INF;
    while(c--){
        int a,b,tmp;
        scanf("%d %d %d",&a,&b,&tmp);
        mp[a].push_back((node){b,tmp});
        mp[b].push_back((node){a,tmp});
    }
    spfa(ts);
    printf("%d\n",dis[te]);
    return 0;
}