ShareText.Cn

min_jump
  1. #include<iostream>
  2. #include<vector>
  3. #include<string>
  4. #include<algorithm>
  5. #include<stack>
  6.  
  7. using namespace std;
  8.  
  9. int get_index(vector<string>& vs, string str){
  10.     vector<string>::iterator it = find(vs.begin(), vs.end(), str);
  11.     if(it == vs.end()){
  12.         vs.push_back(str);
  13.         return vs.end() - vs.begin() - 1;
  14.     }
  15.     else return it - vs.begin();
  16. }
  17.  
  18. struct Node{
  19.     string data;
  20.     int id;
  21.     struct Node* next;
  22.     Node(string d, int i, struct Node *n=null) {
  23.         data = d;
  24.         id = i;
  25.         next = n;
  26.     }
  27. };
  28.  
  29. typedef pair<Node*, int> node_l;
  30.  
  31. int dfs(vector<Node*> graph, int start_id, int end_id){
  32.     vector<int> vlen;
  33.     stack<pair<Node*, int> > sn;
  34.     Node* ps = graph[start_id];
  35.     pair<Node*, int> tmp(ps, 0);
  36.     sn.push(tmp);
  37.     while(!sn.empty()){
  38.         pair<Node*, int> nl = sn.top();
  39.         sn.pop();
  40.         Node* p = nl.first;
  41.         int level = nl.second;
  42.         if(p->id == end_id){
  43.             vlen.push_back(level);
  44.             continue;
  45.         }
  46.         else{
  47.             p = p->next;
  48.             while(p){
  49.                 tmp = make_pair(graph[p->id], level + 1);
  50.                 sn.push(tmp);
  51.                 p = p->next;
  52.             }
  53.         }
  54.     }
  55.     return *min(vlen.begin(), vlen.end());
  56. }
  57.  
  58. int main(){
  59.     ios::sync_with_stdio(false);
  60.     vector<string> vs;
  61.     string start, end;
  62.     getline(cin, start, ',');
  63.     getline(cin, end);
  64.     string from, to;
  65.     vector<Node*> graph;
  66.     // 建图,邻接表法表示
  67.     while(!cin.eof()){
  68.         getline(cin, to, ',');
  69.         if(to=="") break;
  70.         int id_to = get_index(vs, to);
  71.         if(id_to >= graph.size()){
  72.             Node *nn = new Node(to, id_to);
  73.             graph.push_back(nn);
  74.         }
  75.         getline(cin, from);
  76.         int id_fr = get_index(vs, from);
  77.         if(id_fr >= graph.size()){
  78.             Node *nn_f = new Node(from, id_fr);
  79.             graph.push_back(nn_f);
  80.         }
  81.         Node *p, *q;
  82.         bool flag = true;
  83.         for(p = graph[id_fr]; p != null; p = p->next){
  84.             q = p;
  85.             if(q->data == to) flag = false;
  86.         }
  87.         if(flag){
  88.             Node *nn = new Node(to, id_to);
  89.             nn->next = null;
  90.             q->next = nn;
  91.         }
  92.     }
  93.     int start_id = get_index(vs, start);
  94.     int end_id = get_index(vs, end);
  95.     cout << dfs(graph, start_id, end_id) << endl;
  96.     return 0;
  97. }
Parsed in 0.017 seconds