Shortest Path in Weighted Graph : (Using Dijkstra)

## SP in Weighted Graph.cpp
#include<bits/stdc++.h>

using namespace std;

vector<int>d;
vector< vector< pair<int,int> > >graph;
vector<bool>mark;

void dijkstra(int s,int n){
    int u,i;
    d[s]=0;
    pair<int,int>p;
    set< pair<int,int> >st;
    for(int i=1;i<=n;i++)
    st.insert(make_pair(d[i],i));
    while(!st.empty()){
        u=st.begin()->second;
        mark[u]=true;
        st.erase(st.begin());
        for(i=0;i<graph[u].size();i++){
            p=graph[u][i];
            if(d[u]+p.second<d[p.first] && mark[p.first]==false){
                st.erase(make_pair(d[p.first],p.first));
                d[p.first]=d[u]+p.second;
                st.insert(make_pair(d[p.first],p.first));
            }
        }
    }
}

int main()
{
    int n,m,u,v,w,i,t,j,a,b;
    cout<<"Enter the no of vertices..";
    cin>>n;

    mark.resize(n+1);
    graph.resize(n+1);
    d.resize(n+1);

    cout<<"\nEnter the number of edges...";
    cin>>m;
    cout<<"\nEnter the edges along with their weights...\n";
    for(i=1;i<=m;i++){
        cin>>u>>v>>w;
        graph[u].push_back(make_pair(v,w));
        graph[v].push_back(make_pair(u,w));
    }

    // Calculating the single source shortest paths...
    fill_n(mark.begin(),n+1,false);
    fill_n(d.begin(),n+1,INT_MAX);
    cout<<"\nEnter the source and destination...";
    cin>>u>>v;
    dijkstra(u,n);
    cout<<"\nThe Shortest distance is..."<<d[v]<<endl;

    return 0;
}