2023.05.10-暑期实习-第三题-快乐校园跑

TaZi SU @ 8 months ago

思路：floyd最短路

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

floyd算法：

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

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

$i$ 到 $j$ 有直达的路，所以直接从 $i$ 前往 $j$
通过另一个点 $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

n, m = map(int, sys.stdin.readline().split())
Map = [[float('inf')] * 105 for _ in range(105)]
f = [[float('inf')] * 105 for _ in range(105)]
a = [0] * 105
s = 0

for i in range(1, m + 1):
    x, y, t = map(int, sys.stdin.readline().split())
    if x != y:
        Map[x][y] = t
    else:
        a[x] = t

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i != j:
            Map[i][j] += a[j]  # 更新从i到j所需要时间加上玩游戏的时间

for i in range(1, n + 1):
    f[i][i] = 0  # 由于玩游戏时间已经加在路程时间上了，因此从i到i时间应该为0

# 求解
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            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])

s = int(sys.stdin.readline())
sum = 0
maxx = 0

for i in range(1, n + 1):
    if i == s:
        continue
    if f[s][i] < float('inf'):
        sum += 1
        maxx = max(maxx, f[s][i])

print(sum + 1, maxx)

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();
        int[][] Map = new int[105][105];
        int[][] f = new int[105][105];
        int[] a = new int[105];
        int s;

        // floyd算法
        // 初始化
        // 初始化为极大值
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = Integer.MAX_VALUE / 2;
            }
        }

        for (int i = 1; i <= m; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int t = scanner.nextInt();
            if (x != y) {
                Map[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) {
                    Map[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] = Math.min(f[i][j], f[i][k] + a[k]);
                    } else { // 中继点和终点不同，通过中继点更新
                        f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]);
                    }
                }
            }
        }

        s = scanner.nextInt();
        int sum = 0;
        int maxx = 0;
        for (int i = 1; i <= n; i++) {
            if (i == s) {
                continue;
            }
            if (f[s][i] < Integer.MAX_VALUE / 2) {
                sum++;
                maxx = Math.max(maxx, f[s][i]);
            }
        }

        System.out.println((sum + 1) + "\n" + maxx); // 别忘记答案加上起点
    }
}

Go

package main

import (
	"fmt"
)

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	var n, m int
	fmt.Scanf("%d %d", &n, &m)
	Map := make([][]int, 105)
	f := make([][]int, 105)
	for i := range Map {
		Map[i] = make([]int, 105)
		f[i] = make([]int, 105)
	}
	a := make([]int, 105)
	var s int

	// floyd算法
	// 初始化
	// 初始化为极大值
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			f[i][j] = 1 << 30
		}
	}

	for i := 1; i <= m; i++ {
		var x, y, t int
		fmt.Scanf("%d %d %d", &x, &y, &t)
		if x != y {
			Map[x][y] = t
		} else {
			a[x] = t
		}
	}

	// 更新从i到j所需要时间加上玩游戏的时间
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			if i != j {
				Map[i][j] += a[j]
			}
			f[i][j] = Map[i][j]
		}
	}

	// 求解
	for k := 1; k <= n; k++ {
		for i := 1; i <= n; i++ {
			for 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])
				}
			}
		}
	}

	fmt.Scanf("%d", &s)
	sum := 0
	maxx := 0
	for i := 1; i <= n; i++ {
		if i == s {
			continue
		}
		if f[s][i] < 1<<30 {
			sum++
			maxx = max(maxx, f[s][i])
		}
	}

	fmt.Printf("%d\n%d\n", sum+1, maxx) // 别忘记答案加上起点
}

Js

function min(a, b) {
  return a < b ? a : b;
}

function max(a, b) {
  return a > b ? a : b;
}

function main() {
  const readline = require('readline');
  const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
  });

  rl.on('line', function(line) {
    const input = line.trim().split(' ').map(Number);
    const n = input[0];
    const m = input[1];
    const Map = Array.from({ length: 105 }, () => Array(105).fill(0));
    const f = Array.from({ length: 105 }, () => Array(105).fill(0));
    const a = Array(105).fill(0);
    let s;

    // floyd算法
    // 初始化
    // 初始化为极大值
    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
        f[i][j] = Infinity;
      }
    }

    let count = 0;
    rl.on('line', function(line) {
      const input = line.trim().split(' ').map(Number);
      const x = input[0];
      const y = input[1];
      const t = input[2];
      if (x !== y) {
        Map[x][y] = t;
      } else {
        a[x] = t;
      }
      count++;
      if (count === m) {
        rl.close();
      }
    });

    rl.on('close', function() {
      // 更新从i到j所需要时间加上玩游戏的时间
      for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
          if (i !== j) {
            Map[i][j] += a[j];
          }
          f[i][j] = Map[i][j];
        }
      }

      // 求解
      for (let k = 1; k <= n; k++) {
        for (let i = 1; i <= n; i++) {
          for (let 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]);
            }
          }
        }
      }

      rl.on('line', function(line) {
        s = Number(line.trim());

        let sum = 0;
        let maxx = 0;
        for (let i = 1; i <= n; i++) {
          if (i === s) {
            continue;
          }
          if (f[s][i] < Infinity) {
            sum++;
            maxx = max(maxx, f[s][i]);
          }
        }

        console.log((sum + 1) + '\n' + maxx); // 别忘记答案加上起点
      });
    });

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

动态规划

# Submissions

Accepted

Uploaded By

TaZi

1 solutions

思路：floyd最短路

代码

C++

python

Java

Go

Js

Information

Status

Development

Support