题解

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int inf = 0x3f3f3f3f;
    int n,m,u,s,t;
    cin >> n >> m >> s >> t;
    int e[n][n];
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        {
    	if (i == j)e[i][j] = 0;
        else e[i][j] = inf;
      	}
    }
    for (int i=0;i<m;i++)
    {
        int a,b,c;
        cin >>a >> b >> c;
        e[a-1][b-1] = e[b-1][a-1] = min(e[a-1][b-1],c);
    }
	int dis[n];
    for (int i=0;i<n;i++)
    {
      dis[i] = e[s-1][i];
    }
    vector<int> book(n,0);
    book[s-1] = 1;
    for (int i=0;i<n;i++)
    {
        int min1 = inf;
        for (int j=0;j<n;j++)
            {
            if (!book[j] && dis[j] < min1)
            {
                min1 = dis[j];
                u = j;
            }
        }
        book[u] = 1;
        for (int k=0;k<n;k++)
        {
            if (e[u][k] < inf)
            {
                if (dis[k] > dis[u]+e[u][k])
                {
                	dis[k] = dis[u]+e[u][k];
                }
            }
        }
    }
    cout << dis[t-1];
    return 0;
}