CF21D Traveling Graph

    • 14通过
    • 46提交
  • 题目来源 CodeForces 21D
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 500ms / 64MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给定一个有n个顶点,m条边的带边权无向图,要求从顶点1开始经过每一条边至少一次最后回到起点1,要求走过的边权值总和最小。 注意:可能有重边和自环 输入:第一行n,m,之后m行每行一条无向边 输出:一个整数w,代表最小边权和,若无解则输出-1

    Translated by 稀神探女

    题目描述

    You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).

    输入输出格式

    输入格式:

    The first line of the input contains two integers $ n $ and $ m $ ( $ 1<=n<=15,0<=m<=2000 $ ), $ n $ is the amount of vertices, and $ m $ is the amount of edges. Following $ m $ lines contain edges as a triples $ x,y,w $ ( $ 1<=x,y<=n,1<=w<=10000 $ ), $ x,y $ are edge endpoints, and $ w $ is the edge length.

    输出格式:

    Output minimal cycle length or -1 if it doesn't exists.

    输入输出样例

    输入样例#1: 复制
    3 3
    1 2 1
    2 3 1
    3 1 1
    
    输出样例#1: 复制
    3
    
    输入样例#2: 复制
    3 2
    1 2 3
    2 3 4
    
    输出样例#2: 复制
    14
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。