C++

#include <iostream>

include <vector>

include <queue>

const int INF = 1023456789; const int MAX_SHOT = 1; /* Modify that to 3 for the bonus challenge * or any arbitrary number really */

using namespace std;

struct pos { int dist, city, shots;

pos (int id, int ic, int is) { dist = id; city = ic; shots = is; }

pos () { dist = INF; city = -1; shots = -1; } };

bool operator> (pos lvalue, pos rvalue) { return lvalue.dist > rvalue.dist; }

int main () { vector<vector<int> > tuples;

/* Read in the input. * (But seriously though. * That input format is uncomfortable * for both humans and computers.) */

char c, lc = 0; int lptr = -1, fptr = -1; while (true) { cin >> noskipws >> c;

if (lc == ')' && c != ',') {
  break;
}

if (c == '(') {
  tuples.push_back(vector<int> (3, 0));
  lptr++;
  fptr = 0;
} else if (c == ',') {
  fptr++;
} else if (c >= '0' && c <= '9') {
  tuples[lptr][fptr] *= 10;
  tuples[lptr][fptr] += c - '0';
}

lc = c;

}

/* Find our haven city */

int lastcity = 0; for (int i = 0; i < tuples.size(); i++) { if (tuples[i][0] > lastcity) { lastcity = tuples[i][0]; } else if (tuples[i][1] > lastcity) { lastcity = tuples[i][1]; } }

/* Transform the edge list into an adjacency list form */

vector<vector<pair<int, int> > > adjacency (lastcity + 1, vector<pair<int, int> > (0)); for (int i = 0; i < tuples.size(); i++) { adjacency[tuples[i][0]].push_back(make_pair(tuples[i][2], tuples[i][1])); adjacency[tuples[i][1]].push_back(make_pair(tuples[i][2], tuples[i][0])); }

vector<vector<int> > bdist (lastcity + 1, vector<int> (MAX_SHOT + 1, INF)); vector<vector<pos> > source (lastcity + 1, vector<pos> (MAX_SHOT + 1, pos())); vector<vector<bool> > vis (lastcity + 1, vector<bool> (MAX_SHOT + 1, false));

/* Dijkstra's algorithm */

priority_queue<pos, vector<pos>, greater<pos> > que; que.push(pos(0, 0, 0)); while (!que.empty()) { pos cur = que.top(); que.pop();

if (!vis[cur.city][cur.shots]) {
  vis[cur.city][cur.shots] = true;

  for (int i = 0; i < adjacency[cur.city].size(); i++) {
pair<int, int> next = adjacency[cur.city][i];

if (cur.dist + next.first < bdist[next.second][cur.shots]) {
  bdist[next.second][cur.shots] = cur.dist + next.first;
  source[next.second][cur.shots] = cur;
  que.push(pos(cur.dist + next.first, next.second, cur.shots));
}

if (cur.shots < MAX_SHOT) {
  if (cur.dist < bdist[next.second][cur.shots + 1]) {
    bdist[next.second][cur.shots + 1] = cur.dist;
    source[next.second][cur.shots + 1] = cur;
    que.push(pos(cur.dist, next.second, cur.shots + 1));
  }
}
  }
}

}

/* Find the best amount of shots used * In dense graphs with large MAX_SHOT * it might not actually be MAX_SHOT. */

int bestz = INF, bestshots; for (int i = 0; i <= MAX_SHOT; i++) { if (bdist[lastcity][i] < bestz) { bestz = bdist[lastcity][i]; bestshots = i; } }

/* Deduce an optimal path from the source using the source[][] vector */

vector<pos> path (1, pos(0, lastcity, bestshots)); while (path.back().city != 0 || path.back().shots != 0) { path.push_back(source[path.back().city][path.back().shots]); }

for (int i = path.size() - 1; i > 0; i--) { cout << path[i].city << " " << (path[i].shots != path[i - 1].shots ? "BLAST " : "") << "to " << path[i - 1].city << ", "; } cout << "Reached Last Chance encountering " << bdist[lastcity][bestshots] << " zombies in " << path.size() - 1 - bestshots << " milliseconds." << endl; }