usingnamespace std; #define fast \ ios_base::sync_with_stdio(false); \ cin.tie(NULL); constint N = 3e3 + 10; constint M = 1e6 + 10; constint INF = 0x3f3f3f3f; constlonglong LINF = 0x3f3f3f3f3f3f3f3f; constint mod = 1e9 + 7; constdouble eps = 1e-3; int ans; structnode{ int u,v,w,next; }a[M]; int f[N],cnt; voidadd(int u,int v,int w){ a[++cnt].v = v; a[cnt].w = w; a[cnt].next = f[u]; f[u] = cnt; } longlong T[N], P[N]; int x, n, m, t; longlong dis[N][N], vis[N][N]; voiddijkstra(){ priority_queue<pair<int,pair<int,int>>> q; memset(dis, 0x3f, sizeof dis); memset(vis, 0, sizeof vis); q.push({0, {1,T[1]}}); dis[T[1]][1] = P[1]; while(!q.empty()) { int u = q.top().second.first; int X = q.top().second.second; q.pop(); if(X > x) continue; if(vis[X][u]) continue; vis[X][u] = 1; for (int i = f[u]; i; i = a[i].next) { int v = a[i].v; int w = X + a[i].w + T[v]; if(dis[w][v] > dis[X][u] + P[v]) { dis[w][v] = dis[X][u] + P[v]; q.push({-dis[w][v], {v, w}}); } } } }
intmain(){ ans = INF; cin >> x >> n >> m >> t; for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); add(u, v, t); add(v, u, t); } for (int i = 1; i <= n; i++) { add(i, i, 0); scanf("%d%d", &T[i], &P[i]); } dijkstra(); if(dis[x][1] == LINF) puts("It is a trap."); else cout << dis[x][1] << '\n'; return0; }
usingnamespace std; #define fast \ ios_base::sync_with_stdio(false); \ cin.tie(NULL); constint N = 3e3 + 10; constint M = 2e5 + 10; constint INF = 0x3f3f3f3f; constlonglong LINF = 0x3f3f3f3f3f3f3f3f; constint mod = 1e9 + 7; constdouble eps = 1e-3; structnode { int u, v, w, next; } a[M], b[M]; int f[N], cnt; inlinevoidadd(int u, int v, int w){ a[++cnt].v = v; a[cnt].w = w; a[cnt].next = f[u]; f[u] = cnt; a[++cnt].v = u; a[cnt].w = 0; a[cnt].next = f[v]; f[v] = cnt; } int d[N], cur[N]; int n, m, s, t; boolbfs(){ queue<int> q; memset(d, -1, sizeof d); q.push(s); d[s] = 0; cur[s] = f[s]; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = f[u]; i; i = a[i].next) { int v = a[i].v; if (d[v] == -1 && a[i].w) { d[v] = d[u] + 1; cur[v] = f[v]; if (v == t) returntrue; q.push(v); } } } returnfalse; } intfind(int u, int limit){ if (u == t) return limit; int flow = 0; for (int i = cur[u]; i && flow < limit; i = a[i].next) { cur[u] = i; int v = a[i].v; if (d[v] == d[u] + 1 && a[i].w) { int ff = find(v, min(a[i].w, limit - flow)); if (!ff) d[v] = -1; a[i].w -= ff, a[i ^ 1].w += ff, flow += ff; } } return flow; } intdinic(){ int flow, res = 0; while (bfs()) while (flow = find(s, INF)) res += flow; return res; } intmain(){ int k; cnt = 1; cin >> m >> n >> k; s = 0, t = n + m + 1; for (int i = 1; i <= m; i++) { add(s, i, 1); } for (int i = 1; i <= n; i++) add(i + m, t, 1); for (int i = 1; i <= k; i++) { int u, v; scanf("%d%d", &u, &v); add(u, m + v, 1); } int ans = 0, ans1 = 0; ans = dinic(); memcpy(b, a, sizeof a); for (int i = 1; i <= m; i++) { memcpy(a, b, sizeof b); a[i * 2].w += 2; ans1 = max(ans1, dinic()); } cout << ans + ans1 << '\n'; return0; }