结点选择
题目描述
有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
数据规模与约定
对于20%的数据， n <= 20。
对于50%的数据， n <= 1000。
对于100%的数据， n <= 100000。
权值均为不超过1000的正整数。
输入
第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。
输出
输出一个整数，代表选出的点的权值和的最大值
样例说明
选择3、4、5号点，权值和为 3+4+5 = 12 。
样例输入
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出
12
思路
这题乍一看是一道关于树的搜索的题目,但是看到数据后就放弃了(；´д｀)ゞ，然后想到动态规划，但是想不出来要怎么找状态。后面百度才知道这是一题树形DP，？？？。什么是树形DP，没有学过。
花了点时间学习了一下，差不多理解这题了。
假设 dp[i][1] 表示选择了 i 节点后的权值，dp[i][0]表示不选 i 节点的权值，那么
dp[i][1] += dp[j][0] --> j 表示 i 节点的孩子
dp[i][0] += max(dp[j][0], dp[j][1]) --> j 表示 i 节点的孩子
最后最大权值为 max(dp[1][0], dp[1][1])
代码
java写的不会过，C++写的过了，不知道为啥
import java.io.*;
import java.util.*;
public class Main {
static class Reader {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = new StringTokenizer("");
static String nextLine() throws IOException {
return reader.readLine();
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
static void close() throws IOException {
reader.close();
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(new PrintStream(System.out));
int n = Reader.nextInt();
int[][] dp = new int[100005][2];
for (int i = 1; i <= n; i++) {
dp[i][1] = Reader.nextInt();
}
ArrayList<Integer>[] nodes = new ArrayList[100005];
for (int i = 0; i <= n; i++) {
nodes[i] = new ArrayList<Integer>();
}
for (int i = 0; i < n - 1; i++) {
int v = Reader.nextInt();
int e = Reader.nextInt();
nodes[v].add(e);
nodes[e].add(v);
}
dfs(1, -1, nodes, dp);
out.println(Math.max(dp[1][1], dp[1][0]));
out.flush();
}
static void dfs(int x, int pre, List<Integer> []nodes, int[][] dp) {
for (int i = 0; i < nodes[x].size(); i++) {
int e = nodes[x].get(i);
if (e == pre) continue;
dfs(e, x, nodes, dp);
dp[x][1] += dp[e][0];
dp[x][0] += Math.max(dp[e][0], dp[e][1]);
}
}
}
#include<iostream>
#include<vector>
#include<string.h>
#define MAXN 100005
using namespace std;
vector<int> nodes[MAXN];
int dp[MAXN][2];
int n, v, e;
void dfs(int x, int pre) {
for (int i = 0; i < nodes[x].size(); i++) {
int s = nodes[x][i];
if (s == pre) continue;
dfs(s, x);
dp[x][1] += dp[s][0];
dp[x][0] += max(dp[s][0], dp[s][1]);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> dp[i][1];
}
for (int i = 0; i < n - 1; i++) {
cin >> v >> e;
nodes[v].push_back(e);
nodes[e].push_back(v);
}
dfs(1, 0);
cout << max(dp[1][0], dp[1][1]);
return 0;
}
网络寻路
题目描述
X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。
源地址和目标地址可以相同，但中间节点必须不同。
如下图所示的网络。
1 -> 2 -> 3 -> 1 是允许的
1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。
输入
输入数据的第一行为两个整数N M，分别表示节点个数和连接线路的条数(1<=N<=10000; 0<=M<=100000)。
接下去有M行，每行为两个整数 u 和 v，表示节点u 和 v 联通(1<=u,v<=N , u!=v)。
输入数据保证任意两点最多只有一条边连接，并且没有自己连自己的边，即不存在重边和自环。
输出
输出一个整数，表示满足要求的路径条数。
样例输入
3 3
1 2
2 3
1 3
样例输出
6
思路
这题简单没啥好说的了
代码
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Reader {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = new StringTokenizer("");
static String nextLine() throws IOException {
return reader.readLine();
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
static void close() throws IOException {
reader.close();
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(new PrintStream(System.out));
int n = Reader.nextInt();
int m = Reader.nextInt();
Solution s = new Solution(n);
for (int i = 0; i < m; i++) {
s.addEdge(Reader.nextInt(), Reader.nextInt());
}
out.println(s.dfs());
out.flush();
}
}
class Solution {
private final int MAX_L = 10005;
private int n, ans;
private List<Integer> []map;
private int []vis;
public Solution(int n) {
this.n = n;
this.map = new ArrayList[MAX_L];
for (int i = 1; i <= n; i++) {
map[i] = new ArrayList<Integer>();
}
this.vis = new int[MAX_L];
}
public void addEdge(int v, int e) {
map[v].add(e);
map[e].add(v);
}
public int dfs() {
for (int i = 1; i <= n; i++) {
dfs(i, -1, 0);
}
return ans;
}
private void dfs(int cur, int cnt, int sum) {
if (sum == 3) {
ans++;
return;
}
for (int i = 0; i < map[cur].size(); i++) {
int e = map[cur].get(i);
if (e != cnt) dfs(e, cur, sum + 1);
}
}
}
数的划分
题目描述
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5;
1，5，1;
5，1，1;
问有多少种不同的分法。
输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )
输出：一个整数，即不同的分法。
输入
两个整数 n,k ( 6 < n ≤ 200， 2 ≤ k ≤ 6 )
输出
1个整数，即不同的分法。
样例输入
7 3
样例输出
4
AC代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author : lwj
* createTime : 2020/1/23 13:40
* description : Reprint please indicate the source
*/
public class Main {
static class Reader {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = new StringTokenizer("");
static String nextLine() throws IOException {
return reader.readLine();
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
static void close() throws IOException {
reader.close();
}
}
public static void main(String[] args) throws IOException {
int n = Reader.nextInt();
int k = Reader.nextInt();
Code_2 code_2 = new Code_2(n, k);
code_2.dfs();
}
}
class Code_2 {
private int ans, n, k;
public Code_2(int n, int k) {
this.n = n;
this.k = k;
}
public void dfs() {
this.dfs(0, 0, 1);
System.out.println(ans);
}
private void dfs(int sum, int cnt, int cur) {
if(sum == n && cnt == k) {
ans++;
return;
}
if(cnt >= k) {
return;
}
for (int i = cur; i <= n - cur; i++) {
if(sum + i > n) return;
dfs(sum + i, cnt + 1, i);
}
}
}
#include<stdio.h>
int n, k, ans;
void dfs(int index, int ct, int cnt) {
int i = 0;
if(ct == n && cnt == k) {
ans++;
}
if(cnt >= k) {
return;
}
for(i = index; i <= n - ct; i++) {
if(ct + i > n) {
continue;
}
dfs(i, i + ct, cnt + 1);
}
}
int main() {
scanf("%d %d", &n, &k);
dfs(1, 0, 0);
printf("%d\n", ans);
return 0;
}
危险系数
题目描述
问题描述
抗日战争时期，冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y)：
对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。
本题的任务是：已知网络结构，求两站点之间的危险系数。
输入
输入数据第一行包含2个整数n(2 < = n < = 1000), m(0 < = m < = 2000),分别代表站点数，通道数；
接下来m行，每行两个整数 u,v (1 < = u, v < = n; u != v)代表一条通道；
最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。
输出
一个整数，如果询问的两点不连通则输出-1.
样例输入
7 6
1 3
2 3
3 4
3 5
4 5
5 6
1 6
样例输出
2
思路
主要思路就是去除某个顶点e(e != u && e != v) 后,判断去除e点后,u和v是否还是连通的,如果不连通的话,计数器加一
至于怎么判断连通性,......直接深搜
AC代码
#include<iostream>
#include<string.h>
using namespace std;
int map[1005][1005];
int mp[1005];
int n, m, a, b, ans;
bool f = false;
void dfs(int cur, int p) {
if (cur == b) {
f = true;
return;
}
if (f) return;
for (int i = 1; i <= n; i++) {
if (map[cur][i] == 1 && i != p && mp[i] == 0) {
mp[i] = 1;
dfs(i, p);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> a >> b;
map[a][b] = 1;
map[b][a] = 1;
}
cin >> a >> b;
for (int i = 1; i <= n; i++) {
if (i != a && i != b) {
memset(mp, 0, sizeof(mp));
f = false;
mp[a] = 1;
dfs(a, i);
if (!f) {
ans++;
}
}
}
cout << ans << endl;
return 0;
}
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Reader {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = new StringTokenizer("");
static String nextLine() throws IOException {
return reader.readLine();
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
static void close() throws IOException {
reader.close();
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(new PrintStream(System.out));
int n = Reader.nextInt();
int m = Reader.nextInt();
Solution s = new Solution(n);
for (int i = 0; i < m; i++) {
s.addEdge(Reader.nextInt(), Reader.nextInt());
}
out.println(s.dfs(Reader.nextInt(), Reader.nextInt()));
out.flush();
}
}
class Solution {
private final int MAX_L = 1005;
private int n, ans, flag;
private List<Integer> []map;
private int []vis;
public Solution(int n) {
this.n = n;
this.flag = 0;
this.map = new ArrayList[MAX_L];
for (int i = 1; i <= n; i++) {
map[i] = new ArrayList<Integer>();
}
this.vis = new int[MAX_L];
}
public void addEdge(int v, int e) {
map[v].add(e);
map[e].add(v);
}
public int dfs(int u, int v) {
for (int i = 1; i <= n; i++) {
if (i != u && i != v) {
vis[u] = 1;
dfs(u, v, i);
if (flag == 0) ans++;
Arrays.fill(vis, 0);
flag = 0;
}
}
return ans;
}
private void dfs(int cur, int end, int cnt) {
if (cur == end) {
flag = 1;
return;
}
if (flag == 0) {
for (int i = 0; i < map[cur].size(); i++) {
int e = map[cur].get(i);
if (e != cnt && vis[e] == 0) {
vis[e] = 1;
dfs(e, end, cnt);
}
}
}
}
}
剪格子
题目描述
如下图所示，3 x 3 的格子中填写了一些整数。
我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0。
输入
程序先读入两个整数 m n 用空格分割 (m,n< 10)。
表示表格的宽度和高度。
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。
输出
输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。
样例输入
3 3
10 1 52
20 30 1
1 2 3
样例输出
3
思路
- 首先先判断矩阵总和是奇数还是偶数,如果是奇数的话直接输出0
- 对矩阵每一个点都进行一次深搜,出口就是当sum(当前总和)等于矩阵一半的时候,且包含左上角格子
- 搜完一个点之后记得回溯,清楚标记
AC代码
#include<iostream>
#include<string.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
int map[15][15];
int vis[15][15];
int m, n, sum, half, ans = 250;
void dfs(int x, int y, int ac, int step) {
if (ac == half) {
if(vis[0][0] == 1) {
if(ans > step) ans = step;
return;
}
} else if (ac < half) {
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if(0 <= nx && nx < n && 0 <= ny && ny < m && vis[nx][ny] == 0) {
vis[nx][ny] = 1;
dfs(nx, ny, ac + map[nx][ny], step + 1);
vis[nx][ny] = 0;
}
}
}
}
int main() {
cin >> m >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> map[i][j];
sum += map[i][j];
}
}
if(sum % 2 != 0) {
cout << "0" << endl;
} else {
half = sum / 2;
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
vis[i][j] = 1;
dfs(i, j, map[i][j], 1);
vis[i][j] = 0;
}
}
if(ans == 250) {
cout << "0" << endl;
} else {
cout << ans << endl;
}
}
return 0;
}
大臣的旅费
题目描述
很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入
输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。
输出
输出一个整数，表示大臣J最多花费的路费是多少。
样例输入
5
1 2 2
1 3 1
2 4 5
2 5 4
样例输出
135
思路
- 首先从u dfs找到最远点v ，然后从v开始，dfs找到的最远点一定是树的直径
证明：
如果u->v 和树的直径没有公共点，则可以从树的直径终点到u引一条边，树直径变长了，矛盾
假设交点为k，那么k->v (或者就是v本身) 一定是树直径的一部分，（最优子结构）
这样就证明了v一定在树的直径的端点处，（为什么是端点，因为u->v是最远的，一定是叶子节点）
- 其实可以直接把每个点都深搜一遍,也能找到最长的一条路径,不过这个方法可能会超时
- 还有一点需要注意,由于题目测试数据的原因,不能用邻接矩阵,只能用邻接表
AC代码
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
struct Edge {
int v, e, w;
};
vector<Edge> map[10005];
int vis[10005];
int ans, imax = -999999;
int n, p, q, d, point;
void dfs(int start, int sum) {
vis[start] = 1;
if(sum > imax) {
imax = sum;
point = start;
}
for (int i = 0; i < map[start].size(); i++) {
Edge e = map[start][i];
if(vis[e.e] == 0) {
sum += e.w;
dfs(e.e, sum);
sum -= e.w;
}
}
}
void cal() {
for(int i = 1; i <= imax; i++) {
ans += (i + 10);
}
cout << ans << endl;
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
cin >> p >> q >> d;
Edge e;
e.v = p; e.e = q; e.w = d;
map[p].push_back(e);
e.v = q; e.e = p;
map[q].push_back(e);
}
dfs(1, 0);
memset(vis, 0, sizeof(vis));
dfs(point, 0);
cal();
return 0;
}
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class Reader {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = new StringTokenizer("");
static String nextLine() throws IOException {
return reader.readLine();
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
static void close() throws IOException {
reader.close();
}
}
public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(new PrintStream(System.out));
int n = Reader.nextInt();
Solution s = new Solution(n);
for (int i = 0; i < n - 1; i++) {
s.addEdge(Reader.nextInt(), Reader.nextInt(), Reader.nextInt());
}
out.println(s.dfs());
out.flush();
}
}
class Solution {
static class Edge {
int v, e, w;
public Edge(int v, int e, int w) {
this.v = v;
this.e = e;
this.w = w;
}
}
private List<Edge> []map;
private int V, ans = Integer.MIN_VALUE, cnt;
private int []vis;
public Solution(int V) {
this.V = V;
this.vis = new int[V + 5];
this.map = new ArrayList[10005];
for (int i = 1; i <= V; i++) {
map[i] = new ArrayList<Edge>();
}
}
public void addEdge(int v, int e, int w) {
map[v].add(new Edge(v, e, w));
map[e].add(new Edge(e, v, w));
}
public int dfs() {
dfs(1, 0);
Arrays.fill(vis, 0);
dfs(cnt, 0);
int cs = 0;
for (int i = 1; i <= ans; i++) {
cs += (10 + i);
}
return cs;
}
private void dfs(int cur, int sum) {
vis[cur] = 1;
if (sum > ans) {
ans = sum;
cnt = cur;
}
for (int i = 0; i < map[cur].size(); i++) {
Edge e = map[cur].get(i);
if (vis[e.e] == 0) dfs(e.e, sum + e.w);
}
}
}
水图
题目描述
小w不会离散数学，所以她van的图论游戏是送分的
小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次，最少需要走多少路
输入描述:
第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路
输出描述:
一个数表示答案
输入
3 1
1 2 1
2 3 1
输出
2
备注:
1 ≤ n ≤ 50000 , 1 ≤ w ≤ 2147483647
思路
从一个结点出发要遍历所有的结点，所以每条路径都要走两次，而只有一条路径只用走一次，所以我们只需要找出最长的一条路径让他只走一次就好了，所以最后的结果就是所有边的权值之和的二倍减去最长的一条路径。
AC代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
/**
* @author : lwj
* createTime : 2020/1/22 13:09
* description : Reprint please indicate the source
*/
public class Main {
static class reader {
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer tokenizer = new StringTokenizer("");
static String nextLine() throws IOException {
return read.readLine();
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(read.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static double nextDouble() throws IOException {
return Double.parseDouble(next());
}
static void close() throws IOException {
read.close();
}
}
public static void main(String[] args) throws IOException {
int n = reader.nextInt();
int x = reader.nextInt();
Solution_6 solution_6 = new Solution_6(n);
for (int i = 0; i < n - 1; i++) {
solution_6.addEdge(reader.nextInt(), reader.nextInt(), reader.nextInt());
}
solution_6.dfs(x);
}
}
class Solution_6 {
static class Edge {
int v, e;
long w;
public Edge(int v, int e, long w) {
this.v = v;
this.e = e;
this.w = w;
}
}
private long ans;
private LinkedList<Edge> []map;
private int []vis;
private long sum;
public Solution_6(int n) {
this.map = new LinkedList[n + 5];
this.vis = new int[n + 5];
for (int i = 1; i <= n; i++) {
map[i] = new LinkedList<Edge>();
}
}
public void addEdge(int v, int e, long w) {
sum += w;
map[v].add(new Edge(v, e, w));
map[e].add(new Edge(e, v, w));
}
public void dfs(int start) {
this.search(start, 0);
System.out.println(2 * sum - ans);
}
private void search(int cur, long dis) {
vis[cur] = 1;
if(map[cur].size() == 1 && vis[map[cur].get(0).e] == 1) {
ans = Math.max(ans, dis);
return;
}
for (int i = 0; i < map[cur].size(); i++) {
Edge e = map[cur].get(i);
if(vis[e.e] == 0) {
search(e.e, dis + map[cur].get(i).w);
}
}
}
}
Q.E.D.
