单源最短路径(Dijkstra)

Dijkstra 算法基本流程：
1.初始化dist[1] = 0,其节点的dist标记为正无穷大。
2.找出一个未标记的，dist[x]最小的节点x，然后标记节点x。
3.扫描节点x的所有出边(x,y,z)，若dist[y]>dist[x]+z，更新dist[y]。
4.重复2-3两个步骤，直到所有节点都被标记。
Dijkstra算法是基于贪心算法，它只适用于所有便都是非负整数的图。

#include <iostream>
#include <cstring> 

using namespace std;
const int N = 1001;
int g[N][N];
int dist[N];
bool st[N];
int n,m;

void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    for(int i=1;i<=n-1;i++){
        int x = 0;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(dist[j]<dist[x]||x==0)){
                x = j;
            }
        } 
        st[x] = 1;
        for(int j=1;j<=n;j++){
            dist[j] = min(dist[j],dist[x] + g[x][j]);
        }
    }
}

int main(){
    cin >> n >> m;
    memset(g,0x3f,sizeof(g));
    for(int i=1;i<=n;i++) g[i][i] = 0;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c); 
    }   
    dijkstra();
    for(int i=1;i<=n;i++) cout << dist[i] << endl;
    return 0;
}