Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <iostream>
- #include <string>
- template <typename T> T sqr(T x) { return x * x; }
- template <typename T> T abs(T x) { return x < 0? -x : x; }
- using namespace std;
- const int MAXN = 127;
- const int INF = (int)1e+9;
- int t;
- int n, m, r;
- int a[MAXN][MAXN];
- int h[MAXN], l[MAXN];
- int next[MAXN], prev[MAXN], upd[MAXN], cnt;
- int block;
- int dfs(int x)
- {
- if (upd[x] == cnt) return 0;
- upd[x] = cnt;
- for (int i = 1; i <= n; i++)
- if (a[h[x]][i] == l[x] && i != block && prev[i] == 0)
- {
- next[prev[i] = x] = i;
- return 1;
- }
- for (int i = 1; i <= n; i++)
- if (a[h[x]][i] == l[x] && i != block && dfs(prev[i]))
- {
- next[prev[i] = x] = i;
- return 1;
- }
- return 0;
- }
- int main()
- {
- /*
- freopen("in", "r", stdin);
- freopen("out", "w", stdout);
- */
- memset(upd, 0, sizeof(upd));
- cnt = 0;
- cin >> t;
- while (t--)
- {
- cin >> m >> n >> r;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- a[i][j] = INF;
- for (int i = 1; i <= n; i++)
- a[i][i] = 0;
- memset(prev, 0, sizeof(prev));
- memset(next, 0, sizeof(next));
- for (int i = 1; i <= r; i++)
- {
- int x, y, l;
- cin >> x >> y >> l;
- a[x][y] = a[y][x] = min(a[x][y], l);
- }
- for (int k = 1; k <= n; k++)
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
- /*
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- printf("a[%d][%d] = %d\n", i, j, a[i][j]);
- //*/
- for (int i = 1; i <= m; i++)
- cin >> h[i] >> l[i];
- int c = 0;
- block = 0;
- for (int i = 1; i <= m; i++)
- {
- cnt += 1;
- c += dfs(i);
- // if (c < i) break;
- }
- if (c < m)
- {
- puts("-1");
- }
- else
- {
- bool flag = true;
- for (int i = 1; i <= m && flag; i++)
- {
- block = next[i];
- cnt += 1;
- flag &= !dfs(i);
- }
- if (flag)
- {
- for (int i = 1; i <= m; i++)
- {
- printf("%d", next[i]);
- if (i < m) printf(" ");
- }
- printf("\n");
- }
- else
- {
- puts("-1");
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement