Codeforces 24A. Ring road
2772 단어 문제풀이도론DFScodeforces
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Nowadays the one-way traffic is introduced all over the world in order to improve driving safety and reduce traffic jams. The government of Berland decided to keep up with new trends. Formerly all n cities of Berland were connected by n two-way roads in the ring, i. e. each city was connected directly to exactly two other cities, and from each city it was possible to get to any other city. Government of Berland introduced one-way traffic on all n roads, but it soon became clear that it's impossible to get from some of the cities to some others. Now for each road is known in which direction the traffic is directed at it, and the cost of redirecting the traffic. What is the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other?
Input
The first line contains integer n (3 ≤ n ≤ 100) — amount of cities (and roads) in Berland. Next n lines contain description of roads. Each road is described by three integers ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) — road is directed from city ai to city bi, redirecting the traffic costs ci.
Output
Output single integer — the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other.
Sample test(s)
input
3
1 3 1
1 2 1
3 2 1
output
1
input
3
1 3 1
1 2 5
3 2 1
output
2
input
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42
output
39
input
4
1 2 9
2 3 8
3 4 7
4 1 5
output
0
먼저 그림의 고리를 기록하고 두 가지 방향을 열거하며 출력에 가장 적은 비용을 들인다.
#include <iostream>
#include <cstring>
using namespace std;
int a[111][111];
int n,x,y,t,p,ans1,ans2;
int loop[111];
bool v[111];
void dfs(int e)
{
v[e]=true;
loop[p++]=e;
for (int i=1;i<=n;i++)
{
if (!v[i]&&(a[e][i]>0||a[i][e]>0))
{
dfs(i);
}
}
}
int main()
{
memset(a,0,sizeof(a));
memset(v,0,sizeof(v));
cin>>n;
for (int i=0;i<n;i++)
{
cin>>x>>y>>t;
a[x][y]=t;
}
p=0;
dfs(1);
loop[p]=1;
ans1=0;
ans2=0;
for (int i=0;i<p;i++) ans1+=a[ loop[i] ][ loop[i+1] ];
for (int i=p;i>=1;i--) ans2+=a[ loop[i] ][ loop[i-1] ];
cout<<min(ans1,ans2)<<endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.