daily pastebin goal
40%
SHARE
TWEET

snarknews [SNSS 2012, R3]. B

aropan Aug 19th, 2012 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top