套用一个模板

解题思路:，套用一个没有经过堆优化版本的Dijstra算法模板

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=510;

int g[N][N];  //稠密图用邻接矩阵存储
int dist[N];  //dist[i]表示i节点到源点（下标为u的节点）的距离
bool st[N];   //st[i]用于标记i节点的最短路是否确定，若确定st[i]=true
int n,m;

void Dijkstra(int u) //该模板求节点编号为u的点到图中其他的点的最短距离，
{
    memset(dist,0x3f,sizeof dist);
    dist[u]=0;   //除u号节点外，其他均初始为无穷大
    for(int i=0;i<n;i++) //n次迭代，每次寻找不在st中距离最近的点t
    {
        int t=-1;//t是用来存储当前所访问的点 因为点的编号是从1-n t=-1即为初始化
        for(int j=0;j<n;j++)    //这一步是在遍历遍历 dist 数组，找到一个节点，这个节点是：没有确定最短路径的节点中距离源点最近的点。
            if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
        
        st[t]=true;   //将t加到s中
        
        for(int j=0;j<n;j++) //用t更新其他点的距离
            if(g[t][j]!=0)
                dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    int temp;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&temp);
            if(temp!=0) g[i][j]=temp;
        }
    }
    Dijkstra(m);
    for(int i=0;i<n;i++)
    {
        if(i==m) continue;
        if(dist[i]==0x3f3f3f3f) printf("-1 ");
        else printf("%d ",dist[i]);
    }
    printf("\n");
    
}