oj.uz

답안 #575143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
575143 2022-06-09T18:33:49 Z Antekb Training (IOI07_training) C++14
17 / 100
 2 ms 468 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=20;
int vis[N];
vector<int> E[N];
vector<pair<int, int> > edg;
vector<int> wei;
int n, m;
int ans=1e9, cur;
int go(int v, int p){
	for(int u:E[v]){
		if(u!=p && vis[u])if((vis[v]+vis[u])&1)return 0;
		if(!vis[u]){
			//cout<<u<<"\n";
			vis[u]=vis[v]+1;
			if(!go(u, v))return 0;
			//cout<<u<<"\n";
			vis[u]=0;
		}
	}
	return 1;
}
void solve(int i){
	if(i==edg.size()){
		if(go(1, 0)){
			ans=min(ans, cur);
		}
		for(int i=2; i<=n; i++)vis[i]=0;
		return;
	}
	E[edg[i].st].push_back(edg[i].nd);
	E[edg[i].nd].push_back(edg[i].st);
	solve(i+1);
	E[edg[i].st].pop_back();
	E[edg[i].nd].pop_back();
	cur+=wei[i];
	solve(i+1);
	cur-=wei[i];
}
int main(){
	cin>>n>>m;
	for(int i=0; i<m; i++){
		int u, v, w;
		cin>>u>>v>>w;
		if(w==0){
			E[u].push_back(v);
			E[v].push_back(u);
		}
		else{
			edg.push_back({u, v});
			wei.push_back(w);
		}
	}
	vis[1]=1;
	solve(0);
	cout<<ans;
}

Compilation message

training.cpp: In function 'void solve(int)':
training.cpp:26:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if(i==edg.size()){
      |     ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -