uva10986.cpp

#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>

using namespace std;
const int kmaxvetex = 20001;
const int kmaxedge = 50001;
const int kintmax = 1 << 20;

struct Edge {
  int other;
  int cost;
  Edge(int o, int c)
      :other(o), cost(c)
  { }
  bool friend operator < (const Edge& lhs, const Edge& rhs);
};
bool operator < (const Edge& lhs, const Edge& rhs) {
  if (lhs.other != rhs.other) {
    return lhs.other < rhs.other;
  } else if (lhs.cost != rhs.cost) {
    return lhs.cost < rhs.cost;
  }
  return false;
}
struct Graph {
  Graph() {
    for (int i = 0; i < kmaxvetex; ++i) {
      cost[i] = kintmax;
    }
  }
  void init(int src) { cost[src] = 0; }
  int cost[kmaxvetex];
  // maybe use pair<int, int> here
  map<int, set<Edge> > graph;
};

int nvetex, nline, src, dst;
/*
bool relax(Graph& g, int from, int to, int dis) {
  int newdis = g.cost[from] + dis;
  if (newdis < g.cost[to]) {
    g.cost[to] = newdis;
    return true;
  }
  return false;
}
*/
int dijkstra(Graph& g) {
  set<pair<int, int> > priq;
  priq.insert(make_pair(g.cost[src], src));

  while (!priq.empty()) {
    pair<int, int> top = *priq.begin();
    priq.erase(priq.begin());

    int vertex = top.second;
    if (vertex == dst)
      return g.cost[dst];
    for (set<Edge>::iterator it = g.graph[vertex].begin(),
         itend = g.graph[vertex].end();
         it != itend; ++it) {
      int other = it->other;
      int c = it->cost;

      if (g.cost[other] > g.cost[vertex] + c) {
        if (g.cost[other] != kintmax) {
          priq.erase(priq.find(make_pair(g.cost[other], other)));
        }
        g.cost[other] = g.cost[vertex] + c;
        priq.insert(make_pair(g.cost[other], other));
      }
    }
  }
  return -1;
}

int main() {
  int ncase;
#ifndef ONLINE_JUDGE
  freopen("in.in", "r", stdin);
#endif
  while (scanf("%d", &ncase) != EOF) {
    for (int i = 0; i < ncase; ++i) {
      Graph g;
      scanf("%d%d%d%d", &nvetex, &nline,
            &src, &dst);
      g.init(src);
      while (nline--) {
        int from, to, cost;
        scanf("%d%d%d", &from, &to, &cost);
        g.graph[from].insert(Edge(to, cost));
        g.graph[to].insert(Edge(from, cost));
      }
      printf("Case #%d: ", i + 1);
      int ans = dijkstra(g);
      if (ans != -1) {
        printf("%d\n", ans);
      } else {
        printf("unreachable\n");
      }
    }
  }
  return 0;
}