dijkstra最短路

重点：无法判负环！！！！！

（判负环可以SPFA，Floyd）

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

int mp[1000][1000],vist[1000],dist[1000];

int main()

{

int n,m,c;

cin>>n>>m>>c;

for(int i=1;i<=m;i++)

{

int x,y,j;

cin>>x>>y>>j;

mp[x][y]=j;

mp[y][x]=j;

}

memset(dist,127,sizeof(dist));

dist[c]=0;

for(int imm=1;imm<n;imm++)

{

int minn=21000000;

int s=0;

for(int i=1;i<=n;i++)

{

if(dist[i]<minn&&vist[i]==0)

{

minn=dist[i];

s=i;

}

}

vist[s]=1;

for(int i=1;i<=n;i++)

{

if(vist[i]==0&&mp[s][i]!=0&&dist[i]>dist[s]+mp[s][i]) dist[i]=dist[s]+mp[s][i];

}

}

for(int i=1;i<=n;i++)

{

cout<<dist[i]<<" ";

}

}