最短路

使用条件：
单源最短路
无负边条件

朴素 Dijkstra 算法

用邻接矩阵存储

//Dijkstra   1.初始化   2.循环  3.  找到未在S中最小的dist  然后把它加入S 并用其来更新其他点的dist

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>

using namespace std;
const int N=510,M=100010;
int n,m;
int g[N][N],d[N];
bool s[N];
int Dijkstra()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;

    for(int i=1;i<=n-1;i++)
    {
        int t=0;
        for(int j=1;j<=n;j++)
        {
            if(!s[j] && (t==0 || d[j]<d[t])) t=j;
        }
        s[t]=true;
        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()
{
    memset(g, 0x3f, sizeof g);
    cin>>n>>m;
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d", &x, &y, &z);
        g[x][y]=min(g[x][y],z);
    }

    cout<<Dijkstra()<<endl;


    return 0;
}