朴素Djikstra算法

算法原理：

集合s ： 当前已经确定最短距离的点
① dis[1] = 0,dis[其他点] = 极大值。
② for( i从1到n）
{
    找到不在s中的 距离最近的点。（设为t）
    把t加入s
    用t更新其他点的距离（看一下从1->x点的距离是否大于1->t->x的距离，如果大于则更新）
 }

存储 稠密图使用邻接矩阵 稀疏图使用邻接表

代码实现待更新。

//acwing 849
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 510;
int n,m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    for (int i=0; i<=n; i ++)
    {
        int t = -1;
        for(int  j = 1;j <= n; j ++)
            if(!st[j] && ( t == -1 || dist[t] > dist[j]))
                t = j;

        if(t==n) break;        //优化
        st[t]= true;
        
        for (int j = 1; j <= n; j ++ )
            dist[j]= min(dist[j],dist[t] + g[t][j]);
    }
    
    if (dist[n]== 0x3f3f3f3f) return -1;
    return dist[n];
}


int main()
{    
    scanf("%d%d",&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] = INF;
    */
    memset(g, 0x3f,sizeof g);

    while(m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b] = min(g[a][b],c);
    }
    int t = dijkstra();

    printf("%d\n",t);
    
    return 0;
}