思路：floyd最短路

通过理解题意我们可以知道，由于组队不限人数，因此答案即为从起点出发，到达其它任一建筑物所需要花费的最长的时间(可以想象队里无数个人，每个人出发只去一个建筑物，最长的时间就是花费最多时间的那个人所耗时)，而最多必经点数则为从起点出发能够到达的点。

floyd算法：

定义 $f[i][j]$ 为从 $i$ 出发到达 $j$ 点所需要花费的时间。

直观理解上，我们从 $i$ 到 $j$ ，无非就是两个选择；

1. $i$ 到 $j$ 有直达的路，所以直接从 $i$ 前往 $j$
2. 通过另一个点 $k$ 作为中继，先去 $k$ ，再从 $k$ 去 $j$

于是其算法方程就出来了：$f[i][j]=min(f[i][j],f[i][k]+f[k][j])$

直观理解就是，在两个路线的方案选择中，选择耗时较少的方案。

于是为了求出任意 $f[i][j]$ ，我们需要枚举 $k,i,j$ 三个变量，每个都可以从 $N$ 个点中选择其一，所以其时间复杂度为$O(N^3)$，一般看到数据量为100左右，就很有可能是该算法。

在本题中，需要稍稍做点修改：

其中，$a[i]$ 为在 $i$ 点做游戏所需要的时间。可以就着原理稍微理解一下。

if(k==j){// 中继点和终点相同，相当于直接从i前往j 
    f[i][j]=min(f[i][j],f[i][k]+a[k]);
}else{// 中继点和终点不同，通过中继点更新 
    f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}

代码

C++

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int n,m;
int Map[105][105];
int f[105][105];
int a[105];
int s;

int main(){
	scanf("%d %d",&n,&m);
	// floyd算法
	// 初始化 
	// 初始化为极大值 
	memset(f,0x3f,sizeof(f));
	for(int i=1,x,y,t;i<=m;++i){
		scanf("%d %d %d",&x,&y,&t);
		if(x!=y) f[x][y]=t;
		else a[x]=t;
	}
	// 更新从i到j所需要时间加上玩游戏的时间 
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(i!=j) f[i][j]+=a[j];
		}
	} 
	for(int i=1;i<=n;++i) f[i][i]=0;// 由于玩游戏时间已经加在路程时间上了，因此从i到i时间应该为0 
	// 求解 
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(i==j) continue;
				if(k==j){// 中继点和终点相同，相当于直接从i前往j 
					f[i][j]=min(f[i][j],f[i][k]+a[k]);
				}else{// 中继点和终点不同，通过中继点更新 
					f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
				}
			}
		}
	}
	scanf("%d",&s);
	int sum=0,maxx=0;
	for(int i=1;i<=n;++i){
		if(i==s) continue;
		if(f[s][i]<0x3f3f3f3f){
			sum++;
			maxx=max(maxx,f[s][i]);
		}
	}
	printf("%d\n%d",sum+1,maxx);// 别忘记答案加上起点 
	
	return 0;
}

python

import sys

def main():
    # 读取建筑物的数量 n 和路径的数量 m
    n = int(input().strip())
    m = int(input().strip())
    
    # 初始化变量
    inf = float('inf')  # 无穷大，用于表示不可达
    f = [[inf] * (n + 1) for _ in range(n + 1)]  # 邻接矩阵，表示两点之间的最短路径
    a = [0] * (n + 1)  # 每个建筑物的“自耗时”（即自身消耗的时间）

    # 读取路径信息并更新邻接矩阵
    for _ in range(m):
        u, v, r = map(int, input().strip().split())  # u->v 的时间为 r
        if u != v:
            f[u][v] = r  # 如果 u 和 v 不同，更新路径时间
        else:
            a[u] = r  # 如果 u==v，更新自耗时

    # 将每个建筑物的自耗时加到路径时间中
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i != j:
                f[i][j] += a[j]
    
    # 对角线（自身到自身）的时间设为 0
    for i in range(1, n + 1):
        f[i][i] = 0

    # Floyd-Warshall 算法，求出所有点之间的最短路径
    for k in range(1, n + 1):  # 遍历所有中继点 k
        for i in range(1, n + 1):  # 遍历起点 i
            for j in range(1, n + 1):  # 遍历终点 j
                if i == j:  # 起点和终点相同，跳过
                    continue
                if k == j:  # 如果中继点和终点相同，相当于直接从 i 到 j
                    f[i][j] = min(f[i][j], f[i][k] + a[k])
                else:  # 否则通过中继点 k 更新路径
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j])

    # 读取起点 s
    s = int(input().strip())

    # 统计结果
    reachable_count = 0  # 可到达的点数
    max_time = 0  # 最长耗时
    for i in range(1, n + 1):
        if i == s:  # 跳过起点
            continue
        if f[s][i] < inf:  # 如果能从起点 s 到达 i
            reachable_count += 1
            max_time = max(max_time, f[s][i])  # 更新最长耗时
    
    # 输出结果
    print(reachable_count + 1)  # 包括起点在内的必经点个数
    print(max_time)  # 所有必经点完成跑步的最长时间

if __name__ == "__main__":
    main()

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 任务数量
        int m = scanner.nextInt(); // 不亲和关系的数量

        final int INF = 0x3f3f3f3f; // 定义一个足够大的数作为INF
        int[][] f = new int[n+1][n+1]; // 最短路径矩阵
        int[] a = new int[n+1]; // 每个任务的执行时间

        // 初始化f矩阵为INF，除了f[i][i] = 0
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i != j){
                    f[i][j] = INF;
                }
            }
        }

        // 读取m条不亲和关系
        for(int i=0; i<m; i++){
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int t = scanner.nextInt();
            if(x != y){
                f[x][y] = t; // 设置路径时间
            }
            else{
                a[x] = t; // 设置任务的执行时间
            }
        }

        // 更新f[i][j] += a[j]，表示从i到j的路径时间包括任务j的执行时间
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i != j && f[i][j] < INF){
                    f[i][j] += a[j];
                    // 防止溢出
                    if(f[i][j] >= INF){
                        f[i][j] = INF;
                    }
                }
            }
        }

        // 设置f[i][i] = 0
        for(int i=1; i<=n; i++){
            f[i][i] = 0;
        }

        // Floyd-Warshall算法
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                if(f[i][k] == INF) continue; // 如果i到k不可达，跳过
                for(int j=1; j<=n; j++){
                    if(f[k][j] == INF) continue; // 如果k到j不可达，跳过
                    if(i == j) continue; // 不处理i到i的情况
                    if(k == j){
                        // 中继点和终点相同，相当于直接从i前往j
                        if(f[i][k] + a[k] < f[i][j]){
                            f[i][j] = f[i][k] + a[k];
                        }
                    }
                    else{
                        // 中继点和终点不同，通过中继点更新
                        if(f[i][k] + f[k][j] < f[i][j]){
                            f[i][j] = f[i][k] + f[k][j];
                        }
                    }
                }
            }
        }

        // 读取起始任务编号s
        int s = scanner.nextInt();
        int sum = 0; // 可达任务数量
        int maxx = 0; // 最大路径时间

        for(int i=1; i<=n; i++){
            if(i == s) continue; // 跳过起始任务
            if(f[s][i] < INF){
                sum++;
                if(f[s][i] > maxx){
                    maxx = f[s][i];
                }
            }
        }

        // 输出结果，sum + 1 表示包括起始任务本身
        System.out.println((sum + 1) + "\n" + maxx);
        scanner.close();
    }
}

题目描述

国内大多数高校都会有一个活动，叫做校园跑。校园跑是一种在校园内进行的跑步运动，旨在提高学生的身体素质和团队合作能力。校园跑的规则是，每个参与者都要从自己所在的建筑物出发，沿着校园内的道路跑步，每到一个建筑他们需要到达这个建筑物的必经点，这样他们的手机会自动记录一次该建筑物。每个参与者都要尽可能多地经过必经点，同时也要尽可能快地完成跑步。

每个参与者的成绩由两个指标决定：经过的必经点个数和跑步总时间。经过的必经点个数越多，跑步总时间越短，成绩越好。校园跑不仅可以锻炼身体，还可以增加对校园各个建筑物的了解和认同感。

小明也参加了他的学校的这个活动，由很多个建筑物组成，每个建筑物都有一个编号，从1到 $n$ 。一个学生从某个建筑物开始，沿着校园中的道路跑步。

由于学社联为了丰富这个活动的内容，让这个活动变得更好玩，他们会在一些建筑物的必经点安排一些小游戏，到达必经点后需要完成这些小游戏才能继续进行跑步。

但是仅一个人把学校所有的建筑物都跑完并完成小游戏，又会过于疲惫，于是学社联允许参加的学生们进行组队，以用时最长的那个人的成绩作为最终成绩。

小明和他的同学组成了一支小队（不限人数），他们想知道，从某个建筑物开始跑步，最多能经过多少个必经点，以及完成跑步的最快时间是多少。

我们已经知道了每个建筑物之间跑步的时间，以及每个必经点完成小游戏的时间，这些时间都用 $runTimes$ 列表给出了。

$runTimes[i]$ 表示从建筑物 $u$ 到 $v$ 建筑物的时间是 $runTime$ ，如果 $u$ 和 $v$ 相同，就表示是这个必经点需要玩小游戏的时间。那么，从 $u$ 到 $v$ 的时间就是两者相加。现在给定一个起始建筑物 $x$，请计算出完成跑步后能经过的最多必经点数和最终成绩时间。

输入描述

输入第一行为一个正整数 $n$ ，表示建筑物的个数.($1 \leq n \leq 100$)

输入第二行为一个正整数 $m$ ，表示路径的条数.($1 \leq m \leq 10^4$)

接下来 m 行输入每行为三个正整数 $u,v,runTime$，表示 $runTimes[i]$ 的三个元素，即从 u->v 需要的时间为 $runTime$,但不代表 v->u 也是如此.($1 \leq u,v,runTime \leq 100$)

最后一行输出校园跑的起点 $x$.($1 \leq x \leq n$)

输出描述

输出为2行。第一行输出为最终可经过的的必经点个数，第二行输出这些小明小队全部完成跑步后的具体时间。

样例1

样例输入

5
9
1 2 3
1 3 4
2 4 6
2 5 7
5 5 5
4 4 4
3 3 3
2 2 2
1 1 1
1

样例输出

5
17

样例解释

​ 以建筑物1为起点计算小队最长耗时，分析可能会存在三条最大耗时路径,分别为1->3以及1->2->5以及1->2->4。

​ 第一条路径1->3路径下,总耗时为4(1->3耗时)+3(3自身耗时)=7。第二条路径1->2->5路径下,总耗时为3(1->2耗时)+2(2自身耗时)+7(2->5耗时)+5(5自身耗时)=17。第三条路径1->2->4路径下,总耗时为3(1->2耗时)+2(2自身耗时)+6(2->4耗时)+4(4自身耗时)=15。

​ 所以在此场景下，小队完成跑步的最短时间为38分钟，为可以经过的所有必经点的最长时间。

​ 最终输出结果分两行输出，最终12345五个必经点都可以经过，所以最终输出结果如样例1输出。

样例2

样例输入

5
6
1 2 10
1 3 20
2 4 30
3 4 40
4 5 50
5 1 60
3

样例输出

5
160