前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >CodeForces 24A Ring road(dfs)

CodeForces 24A Ring road(dfs)

作者头像
ShenduCC
发布2018-04-27 10:41:03
6500
发布2018-04-27 10:41:03
举报
文章被收录于专栏:算法修养

A. Ring road

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 ncities 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 nlines contain description of roads. Each road is described by three integers aibici(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.

Examples

input

代码语言:javascript
复制
3
1 3 1
1 2 1
3 2 1

output

代码语言:javascript
复制
1

input

代码语言:javascript
复制
3
1 3 1
1 2 5
3 2 1

output

代码语言:javascript
复制
2

input

代码语言:javascript
复制
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42

output

代码语言:javascript
复制
39

input

代码语言:javascript
复制
4
1 2 9
2 3 8
3 4 7
4 1 5

output

代码语言:javascript
复制
0
代码语言:javascript
复制
深搜
代码语言:javascript
复制
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <vector>
using namespace std;
vector<pair<int,int> >a[105];
vector<pair<int,int> >b[105];
int n;
int num;
int now;
void dfs(int x,int pre)
{
    if(x==now)
        return;
    if(a[x].size()>0&&a[x][0].first!=pre)
        dfs(a[x][0].first,x);
    else if(a[x].size()>1&&a[x][1].first!=pre)
        dfs(a[x][1].first,x);
    else if(b[x].size()>0&&b[x][0].first!=pre)
    {
        num+=b[x][0].second;
        dfs(b[x][0].first,x);
    }
    else if(b[x].size()>1&&b[x][1].first!=pre)
    {
        num+=b[x][1].second;
        dfs(b[x][1].first,x);
    }
}
int main()
{
    scanf("%d",&n);
    int x,y,z;

    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        a[x].push_back(make_pair(y,z));
        b[y].push_back(make_pair(x,z));
    }
    int ans=1e9;
    for(int i=1;i<=n;i++)
    {
        num=0;
        now=i;
        if(a[i].size()>0)
        {
			num=0,now=i;
            dfs(a[i][0].first,i);
            ans=min(ans,num);
        }
        if(a[i].size()>1)
        {
			num=0,now=i;
            dfs(a[i][1].first,i);
            ans=min(ans,num);
        }
        if(b[i].size()>0)
        {
            num=0,now=i;
            num+=b[i][0].second;
            dfs(b[i][0].first,i);
            ans=min(ans,num);
        }
        if(b[i].size()>1)
        {
            num=0,now=i;
            num+=b[i][1].second;
            dfs(b[i][1].first,i);
            ans=min(ans,num);
        }

    }
    printf("%d\n",ans);
    return 0;

}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-05-31 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档