携程附加题 给的例子 是不是错了？
输入
4
0,1,2,3
1,0,4,5
2,4,0,2
3,5,2,0
输出
5
----------------------------
最短路径和不应是7吗
--------------------------------
好吧，我会错意了，以为一定要从第0个城市开始遍历。。。已哭晕@@
2016-09-17 21:15 已编辑 复旦大学 C++
关注
全部评论
lalala、
哈尔滨工业大学 Java
import java.math.BigInteger;
import java.util.*;
public class Main{
static int n;
static int [][] adj;
static boolean vis[];
static int ans = Integer.MAX_VALUE;
public static void main(String [] args)
{
Scanner in = new Scanner(System.in);
while(in.hasNext())
{
n = in.nextInt();
adj = new int[n][n];
vis = new boolean[n];
String rub = in.nextLine();
for(int i = 0; i<n; i++)
{
String str = in.nextLine();
String [] line = str.split(",");
for(int j = 0; j<n; j++)
{
adj[i][j] = Integer.parseInt(line[j]);
}
}
for(int i = 0; i<n; i++)
{
dfs(i, 1, 0);
}
System.out.println(ans);
}
}
static void dfs(int i, int len, int cost)
{
if(len == n)
{
ans = Math.min(ans, cost);
return;
}
if(cost >= ans) return;
vis[i] = true;
for(int j = 0; j<n; j++)
{
if(j!=i && !vis[j])
{
dfs(j, len +1, cost + adj[i][j]);
}
}
vis[i] = false;
}
}
shaakalaka
浙江大学 C++
应该是Dijkstra来做就OK了。。而我完全不知道附加题是编程题。。以为是简答题。。233333最后没时间做了
xzchaoo
蚂蚁集团_技术风险部_高级研发工程师
昏迷了 你们在说什么 这不是 旅行商问题吗 用最小生成树做是错的吧!
EdisonPan
华南农业大学 Java
其实今晚的分值分布是怎样的？
EdisonPan
华南农业大学 Java
输入是不是以字符串输入，然后再切割放到数组里面啊
_.chase(_)
东华大学 Java
最小生成数+限定每个节点的度<2~~
换个马甲就不认识了
重庆大学 Java
唉~你们这些喜欢刷题的好厉害啊~~~~我们这种平时不刷题的完全跟不上你们节奏啊
牛客305214号
浙江科技 Java
最短路径😂😂
盛夏de午夜
腾讯_研发
写完最小生成树，最后十几分钟才发现不是最小生成树，是暴利深搜，结果代码刚调对，时间就到了，我去。。。
额闹尼么斯
用的最暴力的枚举，然后取最小值，AC了 233
doubleff
中国政法大学 C++
mst
牛客142966号
北京交通大学 C++
33% +1
事在人为oh_ho
北京航空航天大学 Java
是不是有向图的最小生成树，最小树形图？
牛客3564599号
Санкт - Петербургский государственный университет экономики и финансов Java
是用旅行家算法吗？ 看题目起点应该是不确定的，我遍历起点，好像超时了
shaakalaka
浙江大学 C++
克鲁斯卡尔
ZzzzzZzz
哈尔滨理工大学 Java
附加题AC的人多吗？一直都只通过33%的测试用例，搞不懂是哪里出问题了
xzchaoo
蚂蚁集团_技术风险部_高级研发工程师
经典问题 竞赛都做烂了
owner
麻省理工 安卓
012354 5步啊 遍历最短路径
Ferran
同济大学 Java
没错，从B->A->C->D.
相关推荐
痴心的社畜希望被of...：我说白了你忽悠他说这周入职拿了offer 再拖
点赞 评论 收藏
分享
