单源最短路 Dijkstra算法 从起点到其他顶点的最短距离 边权非负
模板代码：
#include<stdio.h>#include<iostream>#include<algorithm>using namespace std;const int MAXV = 1000; //最大顶点数const int INF = 0x3fffffff; //设一个很大的数int n,m,s,G[MAXV][MAXV]; //顶点数、边数、起点、保存图int d[MAXV]; //起点到各个点的最短距离 也就是最终结果bool vis[MAXV] = {false}; //标记是否访问 访问了变为truevoid Dijkstra(int s){ //s为起点fill(d,d+MAXV,INF); //初始化全为最大值d[s] = 0; //到自己距离为0for(int i=0;i<n;i++){int u = -1, MIN = INF;for(int j=0;j<n;j++){if(vis[j] == false && d[j] < MIN){ //从没被访问的挑一个距离最小值u = j;MIN = d[j];} }//找不到则说明剩下的顶点和s都连通了if(u == -1) return;vis[u] = true; //标记为访问了for(int v=0;v<n;v++){if(vis[v] == false && G[u][v] != INF && d[u]+G[u][v]<d[v]){d[v] = d[u] + G[u][v];}}}}int main(){int u,v,w;scanf("%d%d%d",&n,&m,&s);fill(G[0],G[0]+MAXV*MAXV,INF);for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);G[u][v] = w;}Dijkstra(s);for(int i=0;i<n;i++)printf("%d ",d[i]);return 0;}
