UVa problem solution 10986 - Sending email

problem link:

Discuss: in this problem you can simply use dijksta algorithm.if you know the algorithm then this problem just direct implementation of that algroithm. there is no tricky part in this problem

try yourself, before see the code



#include<bits/stdc++.h>
#define mx 1e9
using namespace std;
int distan[20005];
bool visited[20005];
typedef std::pair<int,int>pr;
vector<pr>vec[50000];
void dijkstra(int src)
{
    distan[src]=0;
    std::priority_queue<pr, std::vector<pr>,std::greater<pr> >que;
    que.push({0,src});
    while(!que.empty())
    {
        int v=que.top().second;
        int u=que.top().first;
        que.pop();
        if(visited[v])
            continue;
        visited[v]=1;
        int sz=vec[v].size();
        for(int i=0;i<sz;i++)
        {
            int u=vec[v][i].first;
            int w=vec[v][i].second;
            if(distan[v]+w<distan[u])
            {
                distan[u]=distan[v]+w;
                que.push({distan[u],u});
            }
        }
    }
}
int main()
{
    int N;
    cin >>N;
    for(int l=1;l<=N;l++)
    {
        int n,m,s,t,i,j,a,b,w;
        cin >>n>>m>>s>>t;
        for(i=0;i<m;i++)
        {
            cin >>a>>b>>w;
            vec[a].push_back({b,w});
            vec[b].push_back({a,w});
        }
        fill(distan,distan+n,mx);
        fill(visited,visited+n,0);
        dijkstra(s);
        printf("Case #%d: ",l);
        if(distan[t]==1e9)
            cout<<"unreachable"<<endl;
            else
                cout <<distan[t]<<endl;
            for(i=0;i<n;i++)
            {
                vec[i].clear();
            }

    }
    return 0;
}