珠海建设网站公司,上海网络建站模板,福建省建设质量安全协会网站,厦门做网站推广题目链接
Codeforces Round 883 (Div. 3) G. Rudolf and CodeVid-23
思路
因为 n n n最大值为 10 10 10#xff0c;且只有 01 01 01两种状态#xff0c;当作二进制数转化为十进制数后最多只有 1024 1024 1024种。
因为 m m m的最大值为 1 e 3 1e3 1e3#xff0c;因此我们…题目链接
Codeforces Round 883 (Div. 3) G. Rudolf and CodeVid-23
思路
因为 n n n最大值为 10 10 10且只有 01 01 01两种状态当作二进制数转化为十进制数后最多只有 1024 1024 1024种。
因为 m m m的最大值为 1 e 3 1e3 1e3因此我们可以枚举每一种状态 2 n 2^{n} 2n种和每一种药 m m m种通过药的作用和副作用对所有的状态进行连边建图。
最后跑Dijkstra求初始状态到 0 0 0号点的最短路即可。
代码
#pragma GCC optimize(O2)
#pragma GCC optimize(O3)
#include bits/stdc.h
using namespace std;
#define int long long
typedef pairint, intpii;
const int N 2e3 5, M 1e6 5;
const int mod 998244353;
const int inf 0x3f3f3f3f3f3f3f3f;int n, m, maxx;
int d[N], dist[N];
bool st[N];
string s, s1[N], s2[N];
int mp[N][N];
void dijkstra()
{int start 0;for (int i 0; i n; i){if (s[i] 1)start pow(2, n - i - 1);}dist[start] 0;priority_queuepii, vectorpii, greaterpiiq;q.push({0, start});while (q.size()){int u q.top().second;int w q.top().first;q.pop();if (st[u]) continue;st[u] true;for (int v 0; v maxx; v){if (u v) continue;int nw mp[u][v];if (nw inf) continue;if (dist[v] w nw){dist[v] w nw;q.push({dist[v], v});}}}
}
void solve()
{cin n m;cin s;maxx pow(2, n) - 1;for (int i 0; i maxx; i){dist[i] inf;st[i] false;for (int j 0; j maxx; j)mp[i][j] inf;}for (int i 1; i m; i){cin d[i] s1[i] s2[i];}for (int i 1; i m; i){for (int j 0; j maxx; j){string v ;for (int k n - 1; k 0; k--){int bit (j k) 1;if (bit) v.push_back(1);else v.push_back(0);}for (int k 0; k n; k){if (s1[i][k] 1)v[k] 0;}for (int k 0; k n; k){if (s2[i][k] 1)v[k] 1;}int res 0;reverse(v.begin(), v.end());for (int k 0; k n; k){if (v[k] 1)res pow(2, k);}if (j res) continue;mp[j][res] min(mp[j][res], d[i]);}}dijkstra();if (dist[0] inf){cout -1 endl;}else cout dist[0] endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test 1;cin test;for (int i 1; i test; i){solve();}return 0;
}
