猫史档案馆

#include<bits/stdc++.h>
using namespace std;
int inf=0x3f3f3f3f;
int cnt,n,m,s,t,u,curr;
bool S[100000]={0};
int dis[100000];
struct Edge {
    int nexty,z,val;
} edge[100000];
int head[100000];
void add(int a,int b,int c) {//写入
	cnt++;
    edge[cnt].val = b;//权重
    edge[cnt].z = c;//去哪-子节点
    edge[cnt].nexty = head[s];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[s] = cnt;//更新以u为起点上一条边的编号
}
void init() {//初始化
    for(int i=1; i<=n; i++)dis[i]=inf;
}
void Dijkstra() {
    curr=s;
    init();
    cnt = 0;
   while(!S[curr]){
    	S[curr]=true;
        for(int i=head[curr]; i!=0; i=edge[i].nexty){
            if(!S[edge[i].z]&&dis[edge[i].z]>dis[curr]+edge[i].val)
                dis[edge[i].z]=dis[curr]+edge[i].val;//更新操作
        }
		int minn=inf;
        for(int i=1;i<=n;i++) {
            if(!S[i]&&minn>dis[i]){
                minn=dis[i];
                curr=i;
            }
        }
    }
	cout<<dis[t-1];
    return;
}


int main() {
    cin>>n>>m;
    cin>>s>>t;
    for(int i=0; i<m; i++) {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dis[s]=0;
    Dijkstra();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct Edge//前向星存边
{
    int z;//此边的子节点
    int val;//此边的权值
    int nexty;//与它最近的父节点一样的边的编号
}edge[1000000];
int head[20000];//以某点为父节点引出的最后一条边
int cnt=0;//边编号
inline void add(int a,int b,int c)//存边
{
    cnt++;
    edge[cnt].z=b;
    edge[cnt].val=c;
    edge[cnt].nexty=head[a];
    head[a]=cnt;//更新head
}
int main()
{
    bool visit[20000]={0};//是否作为过起点
    long long dis[20000];//距离
    int n,m,s,t;
    int a,b,c;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=n;i++)dis[i]=2147483喵7;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int curr=s;
    dis[s]=0;
    long long minn;
    while(!visit[curr]){
        visit[curr]=true;
        for(int i=head[curr];i!=0;i=edge[i].nexty){
            if(!visit[edge[i].z]&&dis[edge[i].z]>dis[curr]+edge[i].val)
            dis[edge[i].z]=dis[curr]+edge[i].val;
        }
        minn=2147483喵7;
        for(int i=1;i<=n;i++){
            if(!visit[i]&&minn>dis[i]){
                minn=dis[i];
                curr=i;
            }
        }
    }
	cout<<dis[t];
    return 0;
}