Submission

Score: 0

User: House123

Problemset: โชว์ของโลมา

Language: cpp

Time: 0.005 second

Submitted On: 2026-03-18 15:16:17

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main(){
    int e,n,s,p,d;
    unordered_map<int,vector<pair<int,int>>> adj; //tower ID , destination and weight
    set<int> allCity; // have all of the number of city because city doesnt have to be always 0 1 2 3 might be 0 5 4 7
    cin >> e; // get the edege
    cin >> n; // tower start
    //create adjacency list
    for(int i = 0 ; i < e;i++){
        cin >> s >> d >> p;

        adj[s].push_back({d,p});
        //s - > d ; length = p';
        allCity.insert(s);allCity.insert(d);

    }
    //------------------- done with creating adj list --------------- //
    unordered_map<int,long long> dist; //shortest distance if I want to go here || name of city -> best dist
    unordered_map<int,int> parent; //remember which city is connect to with and who they parent are

    for(auto c : allCity){

        //setting default value, distance = INF and no one has parent yet
        dist[c] = INF;
        parent[c] = -1; 
    }

    //setting up pq
    priority_queue<pair<long long,int> , vector<pair<long long,int>> , greater<>> pq; //so when sort it will be easier since we have <distance , city ID>

    dist[n] = 0; //start distance = 0 always !!!!
    pq.push({0,n});

    while(!pq.empty()){
        auto [current_distance , curr_location] = pq.top();
        pq.pop();

        if(current_distance > dist[curr_location]) continue; //if distance of current_location is better than current_distance then skip;

        for(auto &edge : adj[curr_location]){
            //find neighbor
            int next_location = edge.first; //destination ID
            int weight = edge.second; //weight

            if(dist[curr_location] + weight < dist[next_location]){
                //we can reach enext location faster by through curr_location
                dist[next_location] = dist[curr_location] + weight;
                parent[next_location] = curr_location; //make curr_location the parent means need to past curr location first there fore you can reach next_location faster
                pq.push({dist[next_location], next_location}); // make next_location = current location when we move to the next niode
            }
        }
    }

    for(int city : allCity){
        //skip start and no node
        if(city == n || dist[city] == INF) continue;
        vector<int> path; // answer vector;
        //add city inside the vector
        for(int curr = city; curr != -1; curr = parent[curr]){
            path.push_back(curr);
        }

        reverse(path.begin(),path.end());
        for(auto &jk : path){
            cout << jk << " "; 
        }
        cout << '\n';
    }




}