Sadonkorjuu

#include <bits/stdc++.h>
using namespace std; 
#define INF 0x3f3f3f3f
#include<list> 
 
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
 
// This class represents a directed graph using
// adjacency list representation
class Graph {
    int V; // No. of vertices
 
    // In a weighted graph, we need to store vertex
    // and weight pair for every edge
    list<pair<int, int> >* adj;
 
public:
    Graph(int V); // Constructor
 
    //    ction to add an edge to graph
    void addEdge(int u, int v, int w);
 
    // prints shortest path from s
    vector<int> shortestPath(int s);
};
 
// Allocates memory for adjacency list
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<iPair>[V];
}
 
void Graph::addEdge(int u, int v, int w)
{
    adj[u].push_back(make_pair(v, w));
    adj[v].push_back(make_pair(u, w));
}
 
// Prints shortest paths from src to all other vertices
vector<int> Graph::shortestPath(int src)
{
    // Create a priority queue to store vertices that
    // are being preprocessed. This is weird syntax in C++.
    // Refer below link for details of this syntax
    // https://www.geeksforgeeks.org/implement-min-heap-using-stl/
    priority_queue<iPair, vector<iPair>, greater<iPair> >
        pq;
 
    // Create a vector for distances and initialize all
    // distances as infinite (INF)
    vector<int> dist(V, INF);
 
    // Insert source itself in priority queue and initialize
    // its distance as 0.
    pq.push(make_pair(0, src));
    dist[src] = 0;
 
    /* Looping till priority queue becomes empty (or all
    distances are not finalized) */
    while (!pq.empty()) {
        // The first vertex in pair is the minimum distance
        // vertex, extract it from priority queue.
        // vertex label is stored in second of pair (it
        // has to be done this way to keep the vertices
        // sorted distance (distance must be first item
        // in pair)
        int u = pq.top().second;
        pq.pop();
 
        // 'i' is used to get all adjacent vertices of a
        // vertex
        list<pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i) {
            // Get vertex label and weight of current
            // adjacent of u.
            int v = (*i).first;
            int weight = (*i).second;
 
            // If there is shorted path to v through u.
            if (dist[v] > dist[u] + weight) {
                // Updating distance of v
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
 
    // Print shortest distances stored in dist[]
    /*
    printf("Vertex Distance from Source\n");
    for (int i = 0; i < V; ++i)
        printf("%d \t\t %d\n", i, dist[i]);*/

    return dist;
}

// Driver's code
int main()
{

    int amount_of_cities; //gets the number of cities that we will have as input
    int amount_of_paths; // we calculate the amount of path between the cities, which is (amount_of_cities-1)

    int city_identity_number;
    list<int> city_identifier = {}; // this is the list in which we store the value of 1 and 0 that identifies, if the city has a port or a farm.

    list<int> the_list_for_farms = {};   // this is the list that will keep all of the verteces, with the value 1.
    list<int> the_list_for_ports = {};  // this is the list that will keep all the verteces with the value 0.

    

    list<int> the_ordinal_number_of_vertex = {};

    int distance_between_2_cities;  // the rows of input that we will get, basically the distance between 2 points.

    int starting_vertex;
    int end_vertex;
    int the_distance;

    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> amount_of_cities; //input to see how many verteces we will have.

    amount_of_paths = amount_of_cities - 1;

    //int array_of_distances[]

    Graph g(amount_of_cities);

    for (int k = 0; k < amount_of_cities; k++){
        cin >> city_identity_number;
        city_identifier.push_back(city_identity_number);

        if (city_identity_number == 1){
            the_list_for_farms.push_back(k);
        }
        if (city_identity_number == 0){
            the_list_for_ports.push_back(k);
        }
    }


    //cout << "the first loop is done" << endl;

    for (int i = 0; i < amount_of_paths; i++){
        for (int j = 0; j < 3; j++){
            cin >> distance_between_2_cities;
            if (j == 0){
                starting_vertex = distance_between_2_cities-1;
                //the_list_for_farms.insert(distance_between_2_cities)
            }
            if (j == 1){
                end_vertex = distance_between_2_cities-1;
                //the_list_for_ports.insert(distance_between_2_cities)
            }
            if (j == 2){
                the_distance = distance_between_2_cities; 
            }
        }
        g.addEdge(starting_vertex, end_vertex, the_distance);
    }
    // create the graph given in above figure
    //int V = 9;
    //Graph g(V);
 
    // making above shown graph
    /*g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);
    */
 
    // Function call

    vector<int> list_of_distances;

    vector<int> list_for_port_distances;
    



    int shortest_path = 0;

    for (auto i : the_list_for_farms){

        //cout << i << endl;

        list_of_distances = g.shortestPath(i);
        int minDist = INF;
        int distance;
        for (auto l : the_list_for_ports){
            distance = list_of_distances[l];
            if(distance < minDist){
                minDist = distance;
            }
            //list_for_port_distances.push_back(list_of_distances[l])
        }

        shortest_path += minDist;

        //cout << minDist << "its the minDist" << endl;

        //cout << shortest_path << "its the shortest_path" << endl;
        
        //PS. actually the way this for loop is made its the right decision
        
        /* a better way to do it is to make an int variable (or list that contains the ordinal number, with the farm)
         and use it to make a loop, then iterate for every point, then filter out the farm -> farm paths and only include the shortest farm -> port paths.*/

         /* PS. actually you dont have to do whats mentioned above (to filter out the farms and stuff), because in the algorithm its already made,
         you just have to choose thie first (so the shortest) oen */
    }

    cout << shortest_path << endl;


    //g.shortestPath(0);
 
    return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 1, 2

Verdict: ACCEPTED

Test 17

Group: 1, 2

Verdict: ACCEPTED

Test 18

Group: 1, 2

Verdict: ACCEPTED

Test 19

Group: 1, 2

Verdict: ACCEPTED

Test 20

Group: 1, 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 1, 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 1, 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 1, 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED