第五题（NOIP2011）

#include<iostream>
using namespace std;
const int V = 100;
int n, m, ans, e[V][V];
bool visited[V];
void dfs(int x, int len) {
    int i;
    visited[x] = true;
    if (len > ans)
        ans = len;
    for (i = 1; i <= n; i++)
        if (!visited[i] && e[x][i] != -1)
            dfs(i, len + e[x][i]);
    visited[x] = false;
}
int main() {
    int i, j, a, b, c;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            e[i][j] = -1;
    for (i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        e[a][b] = c;
        e[b][a] = c;
    }
    for (i = 1; i <= n; i++)
        visited[i] = false;
    ans = 0;
    for (i = 1; i <= n; i++)
        dfs(i, 0);
    cout << ans << endl;
    return 0;
}

1. 【判断题】输入的数据应满足a, b < 100。
   {{ select(1) }}

• 正确
• 错误

2. 【判断题】该程序实现的是多源最短路。
   {{ select(2) }}

• 正确
• 错误

3. 【判断题】在没有重边与自环的情况下，m最大为n²。
   {{ select(3) }}

• 正确
• 错误

4. 【判断题】对于一个n个点的边权均为w的完全图，输出为(n-1) * w。
   {{ select(4) }}

• 正确
• 错误

5. 【选择题】求该程序消耗空间约为（ ）。
   {{ select(5) }}

• 100MB
• 1GB
• 40KB
• 100KB

6. 【选择题】输入为：
   4 6
   1 2 10
   2 3 20
   3 4 30
   4 1 40
   1 3 50
   2 4 60
   输出为（ ）。
   {{ select(6) }}

• 150
• 60
• 210
• 10