QZX

2628

Foraino0267
ACWing的用户
Tenko_
yxc

itdef
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

zombotany

QZX
4天前

## 这题着实有些恶心人了。

#include<iostream>
#include<string>
using namespace std;

inline void OutPutAnswer(int wScore, int lScore)
{
cout<<wScore<<':'<<lScore<<endl;
}

int main(){
char input;
string races;
while(!cin.fail()){
cin>>input;
if(input>='A'&&input<='Z'){
races+=input;
}
if(input=='E'){
break;
}
}
cin.clear();

int wScore=0,lScore=0;
int rounds=0;
//11
for(auto race:races){
if(race=='E'){
}
if(race=='W')wScore++;
if(race=='L')lScore++;
if((wScore>=11||lScore>=11)&&abs(wScore-lScore)>=2){
wScore=lScore=0;
rounds++;
}
}
puts("");
//21
wScore=0;lScore=0;
rounds=0;
for(auto race:races){
if(race=='E'){
if(wScore!=0||lScore!=0||rounds==0){
}else{
break;
}
}
if(race=='W')wScore++;
if(race=='L')lScore++;
if((wScore>=21||lScore>=21)&&abs(wScore-lScore)>=2){
wScore=lScore=0;
rounds++;
}
}
return 0;
}


QZX
6天前

QZX
7天前

## 2022.8.8

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

#define MAX_N 100010

enum Color{
WHITE,
BLACK,
EMPTY
};

Color ReverseColor(Color color){
if(color == WHITE)
return BLACK;
else if(color == BLACK)
return WHITE;
else
return EMPTY;
}

vector<int> edges[MAX_N];
Color color[MAX_N];
int n, m;

bool BFSDye(int startId){
queue<int> q;
q.push(startId);
color[startId] = BLACK;

while(q.size()){
int currentNode=q.front();
q.pop();

for(auto next:edges[currentNode]){
if(color[next] == EMPTY){
color[next] = ReverseColor(color[currentNode]);
q.push(next);
}
else if(color[next] == color[currentNode]){
return false;
}
}
}
return true;
}

int main(){
cin >> n >> m;
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
}

//init color
for(int i = 1; i <= n; i++){
color[i] = EMPTY;
}

for(int i = 1; i <= n; i++){
if(color[i] == EMPTY){
if(!BFSDye(i)){
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes" << endl;
return 0;
}


QZX
7天前

## 2022.8.8

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_N 100010

struct Edge{
int from,to,weight;
bool operator<(const Edge& e) const{
return weight<e.weight;
}
};

vector<Edge> edges;
//并查集记录是否连通
int father[MAX_N];

int QueryAncestor(int id){
if(father[id]==0) return id;
//返回并且路径压缩
return father[id]=QueryAncestor(father[id]);
}

inline bool HaveSameAncestor(int id1,int id2){
return QueryAncestor(id1)==QueryAncestor(id2);
}

void Merge(int id1,int id2){
if(HaveSameAncestor(id1,id2)) return;
father[QueryAncestor(id1)]=QueryAncestor(id2);
}

int n,m;
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
edges.push_back((Edge){u,v,w});
}

//sort the edges
sort(edges.begin(),edges.end());

//traverse the edges
int ans=0,count=0;
for(auto edge:edges){
if(!HaveSameAncestor(edge.from,edge.to)){
ans+=edge.weight;
count++;
Merge(edge.from,edge.to);
}
}
//check whether the graph is connected to another
if(count<n-1){
cout<<"impossible"<<endl;
}else{
cout<<ans<<endl;
}
return 0;
}


QZX
11天前

## 2022.8.4

#include<iostream>
#include<cstring>
using namespace std;

#define MAX_N 510
int map[MAX_N][MAX_N];
//点到集合的距离
int dist[MAX_N];
bool isInGather[MAX_N];

int main(){
int n,m;

cin>>n>>m;

//init
memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map[i][j]=0x3f3f3f3f;
}
}

for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
map[a][b]=map[b][a]=min(map[a][b],c);
}

//Prim
for(int i=1;i<=n;i++){
//select min point from not in gather
int minDistancePoint=-1;
for(int j=1;j<=n;j++){
if(!isInGather[j] && (minDistancePoint==-1 || dist[j]<dist[minDistancePoint])){
minDistancePoint=j;
}
}

//判断连通性：
//非第一个点且到集合距离是INF则说明不连通
if(i!=1&&dist[minDistancePoint]==0x3f3f3f3f){
cout<<"impossible"<<endl;
return 0;
}
if(i!=1){
}

isInGather[minDistancePoint]=true;

//update dist
for(int j=1;j<=n;j++){
if(!isInGather[j]){
dist[j]=min(dist[j],map[minDistancePoint][j]);
}
}
}

//DEBUG:
// for(int i=1;i<=n;i++){
//     cout<<dist[i]<<" ";
// }
// puts("");

return 0;
}


QZX
14天前

## 2022.8.1

#include<iostream>
#include<cstring>
using namespace std;

#define MAX_N 210
#define INF 1e9

//dist[i][j]表示从i到j的最短路径长度,一开始的图也用dist存储
int dist[MAX_N][MAX_N];
int n,m,k;

int main(){
cin>>n>>m>>k;

//init
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j]=INF;
if(i==j){
dist[i][j]=0;
}
}
}

while(m--){
int u,v,w;
cin>>u>>v>>w;
dist[u][v]=min(dist[u][v],w);
}

//Calculate shortest path between every pair of points
for(int transitPoint=1;transitPoint<=n;transitPoint++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j]=min(dist[i][j],dist[i][transitPoint]+dist[transitPoint][j]);
}
}
}

//Query
while(k--){
int a,b;
cin>>a>>b;
if(dist[a][b]>=2e8){
cout<<"impossible"<<endl;
}else{
cout<<dist[a][b]<<endl;
}
}
return 0;
}


QZX
15天前

## 2022.7.31

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;

#define MAX_N 2010

struct Edge{
int to,w;
};

vector<Edge> map[MAX_N];
int dist[MAX_N];
//用于记录路径长度
int cnt[MAX_N];
int n,m;

int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
map[u].push_back((Edge){v,w});
}

//spfa

//init
queue<int> updated;
//放置所有点原因:防止存在1点到达不了的负环
for(int i=1;i<=n;i++){
updated.push(i);
}

while(updated.size()){
int point=updated.front();
updated.pop();
for(auto edge:map[point]){
if(dist[edge.to]>dist[point]+edge.w){
dist[edge.to]=dist[point]+edge.w;
updated.push(edge.to);
cnt[edge.to]=cnt[point]+1;
//抽屉原理判断负环
if(cnt[edge.to]>=n){
cout<<"Yes"<<endl;
return 0;
}
}
}
}
cout<<"No"<<endl;
return 0;
}


QZX
15天前

## 2022.7.31

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;

struct Edge{
int to,w;
};

#define MAX_N 100010

vector<Edge> map[MAX_N];
int dist[MAX_N];
int n,m;

int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
int u,v,w;
cin>>u>>v>>w;
map[u].push_back((Edge){v,w});
}

//初始化
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
//记录被更新过的点
queue<int> updated;
updated.push(1);

while(updated.size()){
int point=updated.front();
updated.pop();
for(auto edge:map[point]){
//若可以更新则放入更新队列
if(dist[point]+edge.w<dist[edge.to]){
dist[edge.to]=dist[point]+edge.w;
updated.push(edge.to);
}
}
}

if(dist[n]==0x3f3f3f3f){
cout<<"impossible"<<endl;
}else{
cout<<dist[n]<<endl;
}
return 0;
}


QZX
16天前

## 2022.7.30

#include<iostream>
#include<cstring>
using namespace std;
#define MAX_N 510

int map[MAX_N][MAX_N];
int dist[MAX_N];
bool isShortest[MAX_N];
int n,m;

int main(){
cin>>n>>m;

//init
memset(map,0x3f,sizeof(map));
memset(dist,0x3f,sizeof(dist));

for(int i=1;i<=m;i++){
int from,to,weight;
cin>>from>>to>>weight;
map[from][to]=min(map[from][to],weight);
}

//dijkstra
dist[1]=0;

for(int i=1;i<=n;i++){
//find shortest distance
int shortestPoint=-1;
for(int j=1;j<=n;j++){
if(!isShortest[j] && (shortestPoint==-1 || dist[j]<dist[shortestPoint])){
shortestPoint=j;
}
}

//update
isShortest[shortestPoint]=true;
for(int j=1;j<=n;j++){
dist[j]=min(dist[j],dist[shortestPoint]+map[shortestPoint][j]);
}
}
if(dist[n]==0x3f3f3f3f){
cout<<-1<<endl;
}else
{
cout<<dist[n]<<endl;
}
return 0;
}


QZX
16天前

## 2022.7.30

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define MAX_N 10010

struct Edge{
int from,to,weight;
};

vector<Edge> edges;
int dist[MAX_N];
//backup用于保存上一次的dist,新一次dist在backup基础上推导出
//防止更新[该次更新的边]的边已经变化
int backup[MAX_N];

int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int from,to,weight;
cin>>from>>to>>weight;
edges.push_back({from,to,weight});
}

//初始化
memset(dist,0x3f,sizeof(dist));
dist[1]=0;

for(int updateTime=1;updateTime<=k;updateTime++){
//保存上一个状态
memcpy(backup,dist,sizeof(backup));
for(auto edge:edges){
int from=edge.from,to=edge.to,weight=edge.weight;
//用上一状态更新当前状态
dist[to]=min(dist[to],backup[from]+weight);
}
}
if(dist[n]>1e8){
cout<<"impossible"<<endl;
}else{
cout<<dist[n]<<endl;
}
return 0;
}