Advertisement
aropan

snarknews [SNSS 2012, R3]. B

Aug 19th, 2012
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.14 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <string>
  6.  
  7. template <typename T> T sqr(T x) { return x * x; }
  8. template <typename T> T abs(T x) { return x < 0? -x : x; }
  9.  
  10. using namespace std;
  11.  
  12. const int MAXN = 127;
  13. const int INF = (int)1e+9;
  14.  
  15. int t;
  16. int n, m, r;
  17. int a[MAXN][MAXN];
  18. int h[MAXN], l[MAXN];
  19. int next[MAXN], prev[MAXN], upd[MAXN], cnt;
  20. int block;
  21.  
  22. int dfs(int x)
  23. {
  24.     if (upd[x] == cnt) return 0;
  25.     upd[x] = cnt;
  26.    
  27.     for (int i = 1; i <= n; i++)
  28.         if (a[h[x]][i] == l[x] && i != block && prev[i] == 0)
  29.         {
  30.             next[prev[i] = x] = i;
  31.             return 1;
  32.         }
  33.        
  34.     for (int i = 1; i <= n; i++)
  35.         if (a[h[x]][i] == l[x] && i != block && dfs(prev[i]))
  36.         {
  37.             next[prev[i] = x] = i;
  38.             return 1;
  39.         }
  40.        
  41.     return 0;
  42. }
  43.  
  44.  
  45. int main()
  46. {
  47. /*
  48.         freopen("in", "r", stdin);
  49.         freopen("out", "w", stdout);
  50. */
  51.     memset(upd, 0, sizeof(upd));
  52.     cnt = 0;
  53.    
  54.     cin >> t;
  55.     while (t--)
  56.     {
  57.         cin >> m >> n >> r;
  58.  
  59.         for (int i = 1; i <= n; i++)
  60.             for (int j = 1; j <= n; j++)
  61.                 a[i][j] = INF;
  62.         for (int i = 1; i <= n; i++)
  63.             a[i][i] = 0;
  64.         memset(prev, 0, sizeof(prev));
  65.         memset(next, 0, sizeof(next));
  66.        
  67.         for (int i = 1; i <= r; i++)
  68.         {
  69.             int x, y, l;
  70.             cin >> x >> y >> l;
  71.             a[x][y] = a[y][x] = min(a[x][y], l);
  72.         }
  73.         for (int k = 1; k <= n; k++)
  74.             for (int i = 1; i <= n; i++)
  75.                 for (int j = 1; j <= n; j++)
  76.                     a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
  77. /*                 
  78.             for (int i = 1; i <= n; i++)
  79.                 for (int j = 1; j <= n; j++)
  80.                     printf("a[%d][%d] = %d\n", i, j, a[i][j]);
  81. //*/               
  82.                
  83.         for (int i = 1; i <= m; i++)
  84.             cin >> h[i] >> l[i];
  85.            
  86.         int c = 0;
  87.         block = 0;
  88.         for (int i = 1; i <= m; i++)
  89.         {
  90.             cnt += 1;
  91.             c += dfs(i);
  92. //          if (c < i) break;
  93.         }
  94.        
  95.         if (c < m)
  96.         {
  97.             puts("-1");
  98.         }
  99.         else
  100.         {
  101.             bool flag = true;
  102.             for (int i = 1; i <= m && flag; i++)
  103.             {
  104.                 block = next[i];
  105.                 cnt += 1;
  106.                 flag &= !dfs(i);
  107.             }
  108.            
  109.             if (flag)
  110.             {
  111.                 for (int i = 1; i <= m; i++)
  112.                 {
  113.                     printf("%d", next[i]);
  114.                     if (i < m) printf(" ");
  115.                 }
  116.                 printf("\n");
  117.             }
  118.             else
  119.             {
  120.                 puts("-1");
  121.             }
  122.         }
  123.     }
  124.    
  125.     return 0;
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement