title

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f

struct Vertex {
    int x, y;

    Vertex(int x, int y) : x(x), y(y) {}
};

typedef pair<double, int> iPair;

class Graph {
    int V;
    vector<Vertex> vertices;
    vector<vector<double>> edgeWeights;

public:
    Graph(int V);
    void addVertex(int x, int y);
    void addEdge(int u, int v);
    double euclideanDistance(const Vertex& u, const Vertex& v);
    void shortestPath(int src);
};

Graph::Graph(int V) {
    this->V = V;
    edgeWeights.resize(V, vector<double>(V, INF));
}

void Graph::addVertex(int x, int y) {
    vertices.emplace_back(x, y);
}

void Graph::addEdge(int u, int v) {
    double weight = euclideanDistance(vertices[u], vertices[v]);
    edgeWeights[u][v] = weight;
    edgeWeights[v][u] = weight;
}

double Graph::euclideanDistance(const Vertex& u, const Vertex& v) {
    return sqrt(pow(u.x - v.x, 2) + pow(u.y - v.y, 2));
}

void Graph::shortestPath(int src) {
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
    vector<double> dist(V, INF);

    pq.push(make_pair(0, src));
    dist[src] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (int v = 0; v < V; ++v) {
            if (edgeWeights[u][v] != INF && dist[v] > dist[u] + edgeWeights[u][v]) {
                dist[v] = dist[u] + edgeWeights[u][v];
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    printf("Vertex Distance from Source\n");
    for (int i = 0; i < V; ++i)
        printf("Vertex %d: %.2lf\n", i, dist[i]);

    int destination;
    cout << "Enter your preferred destination vertex: ";
    cin >> destination;

    if (dist[destination] == INF) {
        cout << "No path exists from source to destination." << endl;
    } else {
        cout << "Shortest distance from source to destination: " << dist[destination] << endl;
    }
}

int main() {
    int V = 4;
    Graph g(V);

    g.addVertex(1, 1);
    g.addVertex(1, 5);
    g.addVertex(5, 1);
    g.addVertex(5, 5);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(1, 3);
    g.addEdge(0, 2);

    int source;
    cout << "Enter the source vertex: ";
    cin >> source;
    cout << endl;
    g.shortestPath(source);
    cout<<"\n";
    return 0;
}