Dijkstra's Algorithm for shortest path from single source . Using priority queues in c++.

For storing a graph , make an adjacency list . vector < vector < pair <int ,int > > > v . in the pair , the first integer is the node and the second is the weight .
You need to make a priority queue to extract the node with minimum distance from source .
priority_queue<pair<int,int> , vector< pair<int,int> > , compare > q ;
In the pair , the first stores the node and second stores the distance from source .
Now you need to make a compare function for your priority queue .
class compare{
    public:
    bool operator() (  pair<int, int> p1,  pair<int, int> p2 ){
        return p1.second > p2.second;
    }
};

With this your priority queue will extract the node with minimum distance from source .

For storing a graph . Let there be an edge from X to Y with weight W . then for storing it , write :
v[X].push_back ( make_pair(Y,W ) ;

Here is the main dijkstra's algorithm now .

#include<bits/stdc++.h>
using namespace std;
class compare{
    public:
    bool operator() (  pair<int, int> p1,  pair<int, int> p2 ){
        return p1.second > p2.second;
    }
};
int main(){
    priority_queue<pair<int,int> , vector< pair<int,int> > , compare > q ;
    int n;
    cin>>n;
    vector< vector< pair<int,int> > > v;
    v.clear();
    v.resize(n+10);
    int edges;
    cin>>edges;
    while(edges--){
        int x,y,z;
        cin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }
    int s;
    cin>>s;//source 
    int d[n+1];//array having distances
    for(int i=1;i<=n;i++){
        d[i] = 999999;//initialize all to infinite or a very high value
    }
    d[s] = 0;//distance from source to source is 0
    q.push(make_pair(s,0));
    while(!q.empty()){
        int u = q.top().first;
        q.pop();
        int size = v[u].size();
        for(int i = 0 ; i < size ; i++){
            int vv = v[u][i].first;
            int w = v[u][i].second;
            if(d[vv] > d[u] + w){
                d[vv] = d[u] + w;
                q.push(make_pair(vv,d[vv]));
            }
        }
    }
}

SPOJ::50 : Invitation Cards solution

#include<bits/stdc++.h>
using namespace std;
inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
#define pb push_back
#define mp make_pair
int main(){
    int t=scan();
    while(t--){
        int n=scan(),m=scan();
        vector<pair<int,int> > v[2][100001];
        while(m--){
            int a=scan(),b=scan(),c=scan();
            v[0][a].pb(mp(b,c));
            v[1][b].pb(mp(a,c));
        }
        priority_queue<pair<int,int> > q;
        int d[n+1][2];
        for(int k=0;k<2;k++){
            for(int i=0;i<=n;d[i++][k]=INT_MAX);
            d[1][k]=0;
            q.push(mp(0,1));
            while(!q.empty()){
                int node=q.top().second;
                int weight=-q.top().first;
                q.pop();
                if(weight>d[node][k])continue;
                int x=v[k][node].size();
                for(int i=0;i<x;i++){
                    int next=v[k][node][i].first;
                    int w = v[k][node][i].second;
                    if(d[next][k]>weight+w){
                        d[next][k]=weight+w;
                        q.push(mp(-d[next][k],next));
                    }
                }
            }
        }
        int ans=0;
        for(int i=2;i<=n;i++){
            ans+=d[i][0]+d[i][1];
        }
        printf("%d\n",ans);
    }
}

SPOJ:: Herding Solution

//you need to find the number of disconnected groups in a graph
//can be done by dfs/bfs
#include<bits/stdc++.h>
using namespace std;
inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
vector<pair<int,int> > v[1001][1001];
int ans=0;
bool visited[1001][1001]={0};
void dfs(int i,int j){
    if(visited[i][j]){
        return;
    }
    visited[i][j]=1;
    int x=v[i][j].size();
    for(int z=0;z<x;z++){
        dfs(v[i][j][z].first,v[i][j][z].second);
    }
}
int main(){
    int n=scan(),m=scan();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s=getchar_unlocked();
            while(s<'E'||s>'W'){
                s=getchar_unlocked();
            }
            if(s=='S'){
                v[i][j].push_back(make_pair(i+1,j));
                v[i+1][j].push_back(make_pair(i,j));
                continue;
            }
            if(s=='N'){
                v[i][j].push_back(make_pair(i-1,j));
                v[i-1][j].push_back(make_pair(i,j));
                continue;
            }
            if(s=='E'){
                v[i][j].push_back(make_pair(i,j+1));
                v[i][j+1].push_back(make_pair(i,j));
                continue;
            }
            if(s=='W'){
                v[i][j].push_back(make_pair(i,j-1));
                v[i][j-1].push_back(make_pair(i,j));
                continue;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(!visited[i][j]){
                ans++;
                dfs(i,j);
            }
        }
    }
    printf("%d\n",ans);
}

SPOJ :: 2143: Dependency Problems solution

//If instead of strings we were given with numbers this would have been just a simple topological sorting.
//But we are given strings so instead of int we use string and instead of array we need to use maps .
//To check for duplicates we need to use set .

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<string> vs;
map<string,vs> m;
map<string,int> indeg;
set<string> exist;
queue<string> q;
int ans=0;
int main(){
    char s[10000];
    bool found=1;
    string current;
    set<string> se;
    while(scanf("%s",s)!=EOF){
        if(found){
            current=s;
            found=0;
            se.clear();
            exist.insert(current);
        }
        else if(s[0]=='0'){
            found=1;
        }
        else{
            string ss=s;
            if(se.find(ss)==se.end()){
                indeg[current]++;
                se.insert(ss);
                m[ss].pb(current);
            }
        }
    }
    set<string>::iterator it;
    for(it=exist.begin();it!=exist.end();it++){
        string cur = *it;
        if(indeg[cur]==0){
            ans++;
            q.push(cur);
        }
    }
    while(!q.empty()){
        string temp=q.front();
        q.pop();
        int x=m[temp].size();
        for(int i=0;i<x;i++){
            string next=m[temp][i];
            indeg[next]--;
            if(indeg[next]==0){
                q.push(next);
                ans++;
            }
        }
    }
    printf("%d",ans);
}

SPOJ 3405. Almost Shortest Path solution

This can be solved with 2 Dijkstra's . Use the first one to find all shortest paths , delete those edges and then do another Dijkstra's for answer . This has a time limit of 0.199 seconds so it has to be optimized a lot . My solution passed in 0.01 seconds .


#include<bits/stdc++.h>
using namespace std;
inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
#define pb push_back
#define mp make_pair
class compare{
    public :
    bool operator()(pair<int,int> a,pair<int ,int > b){
        return a.second>b.second;
    }
};
int main(){
    while(1){
        int n=scan(),m=scan();
        if(n==0&&m==0){
            break;
        }
        int s=scan(),d=scan();
        vector<pair<int,int> > v[501];
        priority_queue<pair<int,int>,vector<pair<int,int> >,compare> q;
        while(m--){
            int x=scan(),y=scan(),w=scan();
            v[x].pb(mp(y,w));
        }
        int dist[501];
        memset(dist,-1,sizeof(dist));
        vector<int> prev[501];
        dist[s]=0;
        q.push(mp(s,0));
        while(!q.empty()){
            int node= q.top().first;
            q.pop();
            int x=v[node].size();
            for(int i=0;i<x;i++){
                int next=v[node][i].first;
                int weight=v[node][i].second;
                if(dist[node]+weight<dist[next]||dist[next]==-1){
                    dist[next]=dist[node]+weight;
                    q.push(mp(next,dist[next]));
                    prev[next].clear();
                    prev[next].pb(node);
                }
                else if(weight + dist[node]==dist[next]){
                    prev[next].pb(node);
                }
            }
        }
        if(dist[d]==-1){
            printf("-1\n");
            continue;
        }
        bool mark[501][501]={0};
        queue<int> qu;
        bool visited[501]={0};
        qu.push(d);
        visited[d]=1;
        while(!qu.empty()){
            int node=qu.front();
            qu.pop();
            int x=prev[node].size();
            for(int i=0;i<x;i++){
                mark[prev[node][i]][node]=1;
                if(!visited[prev[node][i]]){
                qu.push(prev[node][i]);
                visited[prev[node][i]]=1;
                }
            }
        }
        int dista[501];
        memset(dista,-1,sizeof(dista));
        dista[s]=0;
        q.push(mp(s,0));
        while(!q.empty()){
            int node= q.top().first;
            q.pop();
            int x=v[node].size();
            for(int i=0;i<x;i++){
                int next =v[node][i].first;
                if(mark[node][next]!=1){
                    int weight= v[node][i].second;
                    if(dista[node]+weight<dista[next]||dista[next]==-1){
                        dista[next]=dista[node]+weight;
                        q.push(mp(next,dista[next]));
                    }
                }
            }
        }
        printf("%d\n",dista[d]);
    }
}

IOI TC Oddsort Solution

#include<bits/stdc++.h>
using namespace std;
inline int scan(){
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9'){
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}
int main(){
    int n,a[5001],dp[5001],sum=0,ma;
    n=scan();
    for(int i=0;i<n;a[i++]=scan(),sum+=a[i-1]);
    for(int i=0;i<n;i++){
        dp[i]=a[i];
        for(int j=0;j<i;j++){
            if(a[i]>=a[j]){
                dp[i]=max(dp[j]+a[i],dp[i]);
            }
        }
        ma=max(ma,dp[i]);
    }
    printf("%d",sum-ma);
}

INOI 2013 Calvins Game solution.

#include<bits/stdc++.h>
using namespace std;
#define s(x) scanf("%lld",&x)
int n;
long long a[1000001]={0};
long long dp[1000001][2];
#define mini INT_MIN
long long rec(int i,bool phase){
    if(dp[i][phase]==-1){
    long long x,y,p=-mini,q=-mini;
    if(i>2){
        x=rec(i-1,0)+a[i-1];
        y=rec(i-2,0)+a[i-2];
    }
    else if(i>1){
        x=rec(i-1,0)+a[i-1];
        y=-mini;
    }
    else{
         x=0;
         y=0;
    }
    if(phase){
        if(i<n-1){
            p=rec(i+1,1)+a[i+1];
            q=rec(i+2,1)+a[i+2];
        }
        else if(i<n){
            p=rec(i+1,1)+a[i+1];
        }
    }
    dp[i][phase]= max(max(p,q),max(x,y));
    }
    return dp[i][phase];
   
}
int main(){
    int k;
    s(n);
    s(k);
    for(int i=1;i<=n;i++){
        s(a[i]);
    }
    memset(dp,-1,sizeof(dp));
    printf("%lld",rec(k,1));
}