Baiye959

1300

HfjNUlYZ

acwing_4380

Bochi

escape_15

JimmyHu
Louisa
lgl405888309
Ethereum
Diana1005
tleee

Baiye959
10天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 600, INF = 0x3f3f3f3f;
int g[N][N], d[N];
bool vis[N];
int n;

int dijkstra(){
memset(d, 0x3f, sizeof d);
d[1]=0;

for(int i=0;i<n-1;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!vis[j] && (t==-1 || d[j]<d[t])) t=j;
}

for(int j=1;j<=n;j++){
d[j]=min(d[j], d[t]+g[t][j]);
}
vis[t]=true;
}

return d[n];
}
int main()
{
memset(g, 0x3f, sizeof g);
int m;
cin >> n >> m;
while(m--){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if(a!=b) g[a][b]=min(g[a][b], c);
}

int ret = dijkstra();
if(ret==INF) cout << -1;
else cout << ret;
return 0;
}


Baiye959
10天前
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

const int N = 100010;
int e[N], ne[N], h[N], idx;
int n, d[N];
int top[N], k;

e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
bool topsort(){
queue<int> q;
for(int i=1;i<=n;i++){
if(!d[i]) q.push(i);
}

while(q.size()){
auto cur = q.front();
top[k++] = cur;
q.pop();
for(int i=h[cur];i!=-1;i=ne[i]){
int j=e[i];
d[j]--;
if(!d[j]) q.push(j);
}
}

return k==n;
}
int main()
{
memset(h, -1, sizeof h);
int m;
cin >> n >> m;
while(m--){
int a, b;
scanf("%d%d", &a, &b);
d[b]++;
}

if(topsort()){
for(int i=0;i<k;i++){
printf("%d ", top[i]);
}
}
else cout << -1;
return 0;
}


Baiye959
13天前

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> heap;
for(int i=0;i<nums.size();i++){
if(heap.count(target-nums[i])){
return {heap[target-nums[i]], i};
}
heap[nums[i]] = i;
//注意在判定后再插入，预防nums[i]==target/2的情况
}
return {};
}
};


Baiye959
13天前

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

const int N = 30;

int n;
bool vis[N];
int g[N][N];

bool bfs(int a, int b){
queue<int> q;
q.push(a);
vis[a]=true;
while(q.size()){
int cur = q.front();
q.pop();
for(int i=0;i<n;i++){
if(vis[i] || !g[cur][i]) continue;
vis[i]=true;
q.push(i);
if(i==b) return true;
}
}
return false;
}
int main()
{
int m;
cin >> n >> m;

while(m--){
int a, b;
scanf("%d%d", &a, &b);
g[a][b]=g[b][a]=1;
}

int a, b;
cin >> a >> b;
if(bfs(a,b)) printf("There is a path between %d and %d.", a, b);
else printf("There is no path between %d and %d.", a, b);
return 0;
}


Baiye959
21天前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;
int m, n;
int h[N], ne[N], e[N], idx;
int d[N], q[N];
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int bfs(){
memset(d, -1, sizeof d);
d[1]=0;

int hh=0, tt=0;
q[0]=1;
while(hh<=tt){
int t = q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(d[j]==-1){
d[j]=d[t]+1;
q[++tt]=j;
}
}
}
return d[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--){
int a, b;
scanf("%d%d", &a, &b);
}

cout << bfs();
return 0;
}


Baiye959
21天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 2*N;
int n;
int h[N], e[M], ne[M], idx;
bool vis[N];
int ans = N;
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u){//返回以u为根的子树中点的数量
vis[u]=true;

int sum=1, res=0;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!vis[j]){
int s = dfs(j);
res = max(res, s);
sum += s;
}
}
res = max(res, n-sum);
ans = min(ans, res);

return sum;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for(int i=0;i<n-1;i++){
int a, b;
scanf("%d%d", &a, &b);
}

dfs(1);
cout << ans;
return 0;
}


Baiye959
22天前
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <string>

using namespace std;

char g[20];
int bfs(string start){
string end = "12345678x";
queue<string> q;
unordered_map<string, int> d;
int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};

q.push(start);
d[start] = 0;
while(q.size()){
string cur = q.front();
q.pop();
if(cur==end) return d[cur];

int dis = d[cur]+1;
int k=cur.find('x');
int x=k/3, y=k%3;
for(int i=0;i<4;i++){
int neX=x+dx[i], neY=y+dy[i];
if(neX>=0 && neX<3 && neY>=0 && neY<3){
swap(cur[neX*3+neY], cur[k]);
if(d.count(cur)==0){
d[cur]=dis;
q.push(cur);
}
swap(cur[neX*3+neY], cur[k]);
}
}
}
// return d[end];
return -1;
}
int main()
{
string state;
char c;
for(int i=0;i<9;i++){
cin >> c;
state += c;
}

// if(state=="12345678x") cout << 0;
// else{
//     int res=bfs(state);
//     if(res) cout << res;
//     else cout << -1;
// }
cout << bfs(state);

return 0;
}


Baiye959
22天前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;
int path[N];
bool vis1[N], vis2[N], col[N];
int n;
char g[N][N];

void dfs(int u){
if(u==n){
for(int i=0;i<n;i++) puts(g[i]);
puts("");
return;
}

for(int i=0;i<n;i++){
if(!col[i] && !vis1[u+i] && !vis2[n-u+i]){
g[u][i]='Q';
col[i]=vis1[u+i]=vis2[n-u+i]=true;
dfs(u+1);
col[i]=vis1[u+i]=vis2[n-u+i]=false;
g[u][i]='.';
}
}
}
int main()
{
cin >> n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
g[i][j]='.';
}
}
dfs(0);
return 0;
}


Baiye959
22天前
#include <iostream>

using namespace std;

const int N = 10;
int n;
int path[N];
bool vis[N];

void dfs(int u){
if(u==n){
for(int i=0;i<n;i++) printf("%d ", path[i]);
printf("\n");
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
path[u]=i;
vis[i]=true;
dfs(u+1);
vis[i]=false;
}
}
}

int main()
{
cin >> n;
dfs(0);
return 0;
}


Baiye959
22天前
#include <iostream>
#include <cstdio>

using namespace std;

//unsigned long long 溢出代替取模2^64
typedef unsigned long long ULL;

const int N = 100010, b=131;
char str[N];
ULL h[N], p[N];

ULL get(int l, int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
int n,m;
scanf("%d%d%s", &n, &m, str+1);
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*b;
h[i]=h[i-1]*b+str[i];
}

while(m--){
int l1,r1,l2,r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if(get(l1, r1)==get(l2, r2)) printf("Yes\n");
else printf("No\n");
}
return 0;
}