Facebook
From Morose Marmoset, 3 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 109
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <queue>
  6. using namespace std;
  7.  
  8. vector<pair<int,int> > vec[1001];
  9. int dist[1000001];
  10. int prv[1000001];
  11.  
  12. int main() {
  13.     string line;
  14.     int y=0;
  15.     int n=0;
  16.     while (1) {
  17.         getline(cin, line);
  18.         if (line == "") break;
  19.         if (line[line.size()-1] != ' ') line += ' ';
  20.         cout<<"line:"<<line<<endl;
  21.         string current = "";
  22.         int x = 0;
  23.         for (int i=0; i<line.size(); i++) {
  24.             char c = line[i];
  25.             if (c == ' ') {
  26.                 int v = stoi(current);
  27.                 int node = 1 + x + y*n;
  28.                 //cout<<"x:"<<x<<" y:"<<y<<" node:"<<node<<" v:"<<v<<endl;
  29.                 if (x == 0 && y == 0) {
  30.                     pair<int,int> p;
  31.                     p.first = v;
  32.                     p.second = node;
  33.                     vec[0].push_back(p);
  34.                 }
  35.                 if (y > 0) {
  36.                     int upper = node - n;
  37.                     //cout<<" upper:"<<upper<<endl;;
  38.                     pair<int,int> p;
  39.                     p.first = v;
  40.                     p.second = node;
  41.                     vec[upper].push_back(p);
  42.                 }
  43.                 if (x > 0) {
  44.                     int left = node - 1;
  45.                     //cout<<" left:"<<left<<endl;
  46.                     pair<int,int> p;
  47.                     p.first = v;
  48.                     p.second = node;
  49.                     vec[left].push_back(p);
  50.                 }
  51.                 current = "";
  52.                 x++;
  53.             } else {
  54.                 current += c;
  55.             }
  56.         }
  57.         //cout<<" po loop x:"<<x<<" y:"<<y<<" n:"<<n<<endl;
  58.         n = x;
  59.         y++;
  60.     }
  61.     int m = y;
  62.  
  63.    priority_queue<pair<int,int>,  std::vector<pair<int,int>>, std::greater<pair<int,int>> > q;
  64.    for (int i=0; i<=n*m; i++) {
  65.        dist[i] = 1000000001;
  66.        prv[i] = -1;
  67.        pair<int,int> p;
  68.        p.first =
  69.        p.second =
  70.        q.push(i);
  71.    }
  72.    dist[0] = 0;
  73.    while(!q.empty()) {
  74.        int u = q.top();
  75.        q.pop();
  76.        int v = vec[u][0].second;
  77.        cout<<"siez:"<<q.size()<<" ";
  78.        cout<<"u:"<<u<<endl;
  79.        cout<<" v:"<<v<<endl;
  80.        if (dist[v] > dist[u] + vec[u][0].first) {
  81.            dist[v] = dist[u] + vec[u][0].first;
  82.            prv[v] = u;
  83.        }
  84.        if (vec[u].size() > 1) {
  85.             int v = vec[u][1].second;
  86.             cout<<" v:"<<v<<endl;
  87.             if (dist[v] > dist[u] + vec[u][1].first) {
  88.                 dist[v] = dist[u] + vec[u][1].first;
  89.                 prv[v] = u;
  90.             }
  91.        }
  92.    }
  93.    cout<<dist[m*n]<<endl;