10986 - Sending email

//el problema no es más que un simple dijkstra, sólo no hay que leer con cin las aristas

#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
#define inf 1000000

void leer(int&a){
 scanf("%d",&a);
}

int main(){
 int test;
 cin>>test;


 for(int tt=1;tt<=test;tt++){
  int n,m,s,t;
  cin>>n>>m>>s>>t;
 
  vector<vector<int> > adj(n);//adyacencia de vértices
  vector<vector<int> > wadj(n);//los pesos de las aristas, este vector es inyectivo a adj
  int a,b,c;
  
  for(int i=0;i<m;i++){
   leer(a);
   leer(b);
   leer(c);
   adj[a].push_back(b);
   adj[b].push_back(a);
   wadj[a].push_back(c);
   wadj[b].push_back(c);
  }
 
  vector<int> dist(n,inf);
  dist[s]=0;
  typedef pair<int,int> pii;
 
  priority_queue<pii,vector<pii>,greater<pii> > q;
  q.push(make_pair(0,s));
  int res=-1;
 
  while(!q.empty()){
   int v=q.top().second;
   int d=q.top().first;
   q.pop();
   if(dist[v]<d) continue;
   if(v==t){res=d;break;}
  
   for(int i=0;i<adj[v].size();i++){
     int u=adj[v][i];
     int nd=wadj[v][i]+d;
     if(nd<dist[u]){
      dist[u]=nd;
      q.push(make_pair(nd,u));
     }
   }
  }
 
  cout<<"Case #"<<tt<<": ";
  if(res==-1) cout<<"unreachable"<<endl;
  else cout<<res<<endl;
 }
}