UVA 10986 Solution - Sending email

UVA 10986 Solution - Sending email

uva id: shoaib05
Accepted Time: 0.379

I used priority queue and Dijkstra Algorithm.

Code:

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#include<cstring>

using namespace std;
typedef pair<int,int> pii;
typedef vector<pii> vecpii;
map<int,vecpii> mymap;
map<int,int> result;
bool visit[20010];

class Compare
{
public:
bool operator()(pii p1,pii p2)
{
return p1.second>p2.second;
}
};

int DjKastra(int x,int y)
{
priority_queue<pii,vector<pii>,Compare> q;
pii p,temp;
int i;
memset(visit,false,sizeof(visit));
q.push(pii(x,0));
while(!q.empty())
{
p=q.top();
if(p.first==y)
return p.second;
q.pop();
if(visit[p.first])
continue;
visit[p.first]=true;
for(i=0;i<mymap[p.first].size();i++)
{
temp=mymap[p.first][i];
if(!visit[temp.first])
{
q.push(pii(temp.first,temp.second+p.second));
}
}
}
return -1;
}

int main() 
{
freopen("file.txt","r",stdin);
int i,x,y,src,dest,w,test_case,kase,n,m;
pii p;
cin>>test_case;
kase=1;
while(kase<=test_case)
{
mymap.clear();
cin>>n>>m>>src>>dest;
if(src==dest)
{
cout<<"Case #"<<kase++<<": 0"<<endl;
continue;
}
for(i=0;i<m;i++)
{
cin>>x>>y>>w;
p=pair<int,int>(y,w);
mymap[x].push_back(p);
p=pair<int,int>(x,w);
mymap[y].push_back(p);
}
memset(visit,false,sizeof(visit));
x=DjKastra(src,dest);
cout<<"Case #"<<kase++<<": ";
if(x==-1)
cout<<"unreachable"<<endl;
else
cout<<x<<endl;

}
return 0;
}