单源最短路

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

---

输入格式(Format Input)

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。 接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度(长度不会超过100)。

输出格式(Format Output)

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为-1）

---

输入样例(Sample Input) 

4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4

输出样例(Sample Output)

0 2 4 3

---

代码(Code)

#include<bits/stdc++.h>
using namespace std;
struct point{
    int e,w;
}; 
vector<point>head[10010];
int n,m,s,dis[10010],used[10010];
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        head[x].push_back(point{y,z});
    }
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;
    for(int i=1;i<=n;i++)
    {
        int Min=1e9,k=0;
        for(int j=1;j<=n;j++)
        {
            if(Min>dis[j]&&used[j]==0)
            {
                Min=dis[j],k=j;
            }
        }
        if(Min==1e9)	break;
        used[k]=1;
        for(int j=0;j<head[k].size();j++)
        {
            int v=head[k][j].e;
            int va=head[k][j].w;
            if(dis[v]>dis[k]+va)	dis[v]=dis[k]+va;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0x7f7f7f7f)
        {
            cout<<-1<<" ";
        }
        else
        {
            cout<<dis[i]<<" ";
         } 
    }
    return 0;
}