Dijkstra算法 朴素版

#include<iostream>
#include<string.h>
using namespace std;
int n,m;
const  int N=5100;
const   int M=100010;
int st[N],d[N];
int g[N][N];
int dijkstra()
{
   
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    for(int i=1;i<=n;i++)
    {
   
        int t=-1;
        for(int j=1;j<=n;j++)
        if(!st[j]&&(t==-1||d[t]>d[j]))
                t=j;
        st[t]=1;
        for(int j=1;j<=n;j++)
        d[j]=min(d[j],d[t]+g[t][j]);
    }
    if(d[n]==0x3f3f3f3f)    return -1;
    else    return d[n];
}
int main()
{
   
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(i==j)    g[i][j]=0;
    else    g[i][j]=0x3f3f3f3f;
    while(m--)
    {
   
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    }
    int t=dijkstra();
    printf("%d\n",t);
    return 0;
}