2012年11月27日

UVa 762 - We Ship Cheap

STL, STL, and STL! lol
#include <cstdio>
#include <string>
#include <map>
#include <set>
#define MP make_pair
using namespace std;
typedef pair<string, string> P;

void print(map<string, string> parent, string now) {
  if (now.compare(parent[now]) == 0) return;
  print(parent, parent[now]);
  printf("%s %s\n", parent[now].c_str(), now.c_str());
}

int main() {
  int n, first = 1;
  while (scanf("%d", &n) == 1) {
    if (!first) puts("");
    first = 0;
    set<string> road;
    set<P> con;
    while (n--) {
      char s1[20], s2[20];
      scanf("%s%s", s1, s2);
      road.insert(string(s1));
      road.insert(string(s2));
      con.insert(MP(string(s1), string(s2)));
      con.insert(MP(string(s2), string(s1)));
    }
    char s[20], e[20];
    scanf("%s%s", s, e);
    map<string, string> parent;
    map<string, int> d;
    set<string> visit;
    for (set<string>::iterator it = road.begin(); it != road.end(); it++)
      d[*it] = 2e9;
    d[s] = 0;
    parent[s] = s;
    while (1) {
      int min = 2e9, flag = 0;
      set<string>::iterator now;
      for (set<string>::iterator it = road.begin(); it != road.end(); it++)
        if (!visit.count(*it) && d[*it] < min) min = d[*it], now = it, flag = 1;
      if (!flag) break;
      visit.insert(*now);
      for (set<string>::iterator it = road.begin(); it != road.end(); it++)
        if (con.count(MP(*it, *now)) && !visit.count(*it) && d[*now] + 1 < d[*it]) {
          d[*it] = d[*now] + 1;
          parent[*it] = *now;
        }
    }
    if (!road.count(s) || !road.count(e) || d[e] == 2e9)puts("No route");
    else print(parent, e);
  }
  return 0;
}

沒有留言:

張貼留言