10986 - Sending email solution

Problem Link: here

Description: 

একটা গ্রাফের এক vertex থেকে আরেক vertex এ সর্বনিম্ন কত কম cost এ যাওয়া যায় তা বের করতে হবে।

solution: 

যেকোন single source shortest path algorithm. এখানে dijkstra algorithm ব্যবহার করা হয়েছে। 

code:

#include<bits/stdc++.h>
using namespace std;
#define MX 20005
#define pii pair<int,int>
vector<pii> adj[MX];
int dis[MX];
void Djakstra(int s)
{
    priority_queue <pii> PQ;
    PQ.push(pii(0,s));
    while(!PQ.empty())
    {
        int u = PQ.top().second;
        PQ.pop();
        for (int i=0;i<adj[u].size();i++)
        {
            int v = adj[u][i].first;
            int w = adj[u][i].second;
            if (dis[u]+w < dis[v])
            {
                dis[v] = dis[u]+w;
                PQ.push(pii(-dis[v],v));
            }
        }
    }
}
int main()
{
    int tc;
    cin>>tc;
    for (int id=1;id<=tc;id++)
    {
        int node,edge,src,dsn;
        scanf("%d%d%d%d",&node,&edge,&src,&dsn);
        int i;
        for (i=0;i<edge;i++)
        {
            int u,v,cost;
            scanf("%d%d%d",&u,&v,&cost);
            adj[u].push_back(pii(v,cost));
            adj[v].push_back(pii(u,cost));
        }
        for (i=0;i<node;i++) dis[i] = 1000000;
        dis[src]=0;
        Djakstra(src);
        if (dis[dsn] == 1000000) printf("Case #%d: unreachable\n",id);
        else printf("Case #%d: %d\n",id,dis[dsn]);
        for (i=0;i<node;i++) adj[i].clear();

    }


}