寻找从源结点到其他点之间的最短距离。

把给出的结点分成两组，一组a刚开始为空，另一组b为全部节点，dis[i]记录从源点到i结点的距离，同样当所有操作结束后dis[i]就是到达源点的最短距离啦，每次更新的时候dis[i]的距离都会缩小。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 int e[100][100],vis[100],dis[100]; 8 int main() 9 {10     int m,n;11     int a,b,c;12     while(cin>>n>>m){13 14 15             ///初始化16             for(int i=1;i<=n;i++){17                 for(int j=1;j<=n;j++){18                         if(i==j)e[i][j]=0;19                 else20                     e[i][j]=inf;21                 }22             }23 24 25         for(int i=1;i<=m;i++){26             cin>>a>>b>>c;27             e[a][b]=c;///c为边a到b的距离28             vis[i]=0;29         }30         for(int i=1;i<=n;i++)31             dis[i]=e[1][i];32         vis[1]=1;///此处的样例代码我们假设1为源点33 34         int u;35         for(int k=1;k<=n-1;k++){
    ///n个结点要遍历n-1次36             int minn=inf;37 ///每次都查找距离1最近的结点38             for(int i=1;i<=n;i++){39                 if(minn>dis[i]&&vis[i]==0){40                         minn=dis[i];41                           u=i;42                 }43             }44 vis[u]=1;45             for(int v=1;v<=n;v++){46             if(e[u][v]
          
           dis[u]+e[u][v])48                     dis[v]=dis[u]+e[u][v];49             }50             }51         }52         for(int i=1;i<=n;i++)53             cout<
           
            <<" ";54 }55 56 }