C++

#include <cstdio>

#include <queue>

#include <vector>

#include <climits>

 

using namespace std;

 

struct Edge

{

    int v;

    int dist;

};

 

const int MAX_N = 20001;

 

vector<Edge> v_vec[MAX_N];

int dist[MAX_N];

 

struct Q_info

{

    int v;

    int dist;

    bool operator < (const Q_info& info) const{

        return dist > info.dist;

    }

};

 

priority_queue<Q_info> pq;

int N,M,S;

 

void dijkstra(int s)

{

    dist[s] = 0;

    pq.push({s, 0});

 

    while(!pq.empty())

    {

        Q_info info = pq.top();

        pq.pop();

        //Q_info info2 = { 1, 3};

        //bool b = info.operator < (info2);

        //bool b2 = info < info2;

 

        if(info.dist != dist[info.v])

            continue;

 

        for(auto &e: v_vec[info.v])

        {

            if(dist[e.v] > info.dist + e.dist)

            {

                dist[e.v] = info.dist + e.dist;

                pq.push({e.v, dist[e.v]});

            }

        }

    }

}

 

int main()

{

    scanf("%d %d %d",&N,&M,&S);

    for(int i=0;i<M;i++){

        int a,b,c;

        scanf("%d %d %d",&a,&b,&c);

        v_vec[a].push_back({b,c});

    }

 

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

        dist[i] = INT_MAX;

 

    dijkstra (S);

    for(int i=1;i<=N;i++){

        if(dist[i]==INT_MAX)

            printf("INF\n");

        else

            printf("%d\n",dist[i]);

    }

 

    return 0;

}