dijkstra算法不能解决含负权边的图，适用于稠密图，和顶点密切相关，时间复杂度，为O(N2)，这个是使用邻接矩阵实现的，当点的数量过多时，该方法的空间复杂度会非常高，甚至会爆栈。
    #include
    using namespace std;
    const int INF = 0x3f3f3f3f;
    const int N = 1e3+5;
    int n,m,k;
    int a[N][N],dis[N],b[N];
    void dijkstra()
    {
    memset(dis,0x3f,sizeof dis);//dis数组初始化
    dis[k]=0;
    for (int i=1;i {
    int minn = INF,u;
    for (int j=1;j<=n;j++)//找到目前结点k所到各个点的最短的边
    {
    if(b[j]==0&&dis[j] {
    minn=dis[j];
    u=j;
    }
    }


    b[u]=1; //将找到的点一一标记
    for (int v=1;v<=n;v++) //对找到的点进行扩展
    {
    if(a[u][v] dis[v]=min(dis[v],dis[u]+a[u][v]);
    }
    }
    }
    int main ()
    {
    cin>>n>>m>>k;
    memset(a,0x3f,sizeof a);
    for(int i=1;i<=n;i++)
    a[i][i]=0;
    for (int i=1;i<=m;i++)
    {
    int u,v,w;
    cin>>u>>v>>w;
    a[u][v]=min(a[u][v],w);
    }
    dijkstra();
    for (int i=1;i<=n;i++)
    cout< return 0;
    }