Advertisement
kokokozhina

C_3

Jul 6th, 2016
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <string>
  4. #include <fstream>
  5. #include <stdio.h>
  6. #include <set>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <queue>
  10.  
  11. using namespace std;
  12.  
  13. int gcd (int a, int b) {
  14.     return b ? gcd (b, a % b) : a;
  15. }
  16.  
  17. struct edge{
  18.     int fr, to, w;
  19. };
  20.  
  21. int main()
  22. {
  23. #ifdef _DEBUG
  24.     freopen("in.txt", "r", stdin);
  25.     freopen("out.txt", "w", stdout);
  26. #endif
  27.     const int INF = 2000000000;
  28.     int dx[] = {-1, 0, 1, 0};
  29.     int dy[] = {0, 1, 0, -1};
  30.     int T, n, m, v1, v2;
  31.     cin >> T;
  32.     vector<edge> g;
  33.     for(int o = 0; o < T; o++){
  34.         cin >> n >> m >> v1 >> v2; v1--, v2--;
  35.         vector<int> w(n, -1);
  36.         g.clear();
  37.         for(int i = 0; i < m; i++){
  38.             int u, v, w; scanf("%D%D%D", &u, &v, &w); u--, v--;
  39.             edge e; e.fr = u, e.to = v, e.w = w;
  40.             g.push_back(e);
  41.         }
  42.        
  43.         vector<int> d(n, INF);
  44.         d[v1] = 0;
  45.         vector<pair<int, int>> p(n);
  46.         for(int i = 0; i < n; i++)
  47.             p[i] = make_pair(-1, 1);
  48.         p[v1] = make_pair(v1, 1);
  49.  
  50.         vector<bool> used(n, false);
  51.         for(int i = 0; i < n; i++){
  52.             //bool up = false;
  53.             for(int z = 0; z < m; z++){
  54.                 int to = g[z].to, from = g[z].fr; //cout << p[to].second << " " << g[z].w << endl;
  55.                 int aux = gcd(p[to].second, g[z].w); cout << aux << endl;
  56.                 if(aux == 1 && (p[to].second != 1 || g[z].w != 1) && d[to] > d[from] + g[z].w)
  57.                     d[to] = d[from] + g[z].w, p[to] = make_pair(from, g[z].w);
  58.             }
  59.         }
  60.  
  61.         if(d[v2] <= INF / 2 + 100){
  62.             vector<int> res;
  63.             for(int i = v2; i != v1; i = p[i].first){
  64.                 res.push_back(i);
  65.             }
  66.             res.push_back(v1);
  67.             reverse(res.begin(), res.end());
  68.             cout << res.size() << " ";
  69.             for(int i = 0; i < res.size(); i++)
  70.                 cout << res[i]+1 << " ";
  71.  
  72.             cout << endl;
  73.         }
  74.         else
  75.             cout << -1 << endl;
  76.  
  77.  
  78.         for(int i = 0; i < n; i++)
  79.             cout << i+1 << " " << p[i].first+1 << " " << p[i].second << endl; cout << endl;
  80.  
  81.     }
  82.  
  83.     return 0;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement