题解 | #游游的旅行#

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

struct Site {
    int m;          // 游玩时间
    double v[2];    // 两人的愉悦度
};

struct Path {
    int d;          // 目标景点
    int t;          // 路径时间
};

// 计算期望愉悦度
double getExpectation(vector<Site>& sites, vector<vector<Path>>& paths, int k, int p) {
    int n = sites.size();
    // dp[i][j]表示剩余i时间在j点的期望愉悦度
    vector<vector<double>> dp(k + 1, vector<double>(n, 0));
    
    for (int i = 1; i <= k; i++) {
        for (int j = 0; j < n; j++) {
            double temp = 0;
            int count = 0;
            
            // 如果时间足够游玩当前景点
            if (i >= sites[j].m) {
                dp[i][j] += sites[j].v[p];
            }
            
            // 考虑所有可达的下一个景点
            for (const Path& path : paths[j]) {
                if (i >= (path.t + sites[j].m + sites[path.d].m)) {
                    temp += dp[i - path.t - sites[j].m][path.d];
                    count++;
                }
            }
            
            // 计算期望值
            if (count) {
                dp[i][j] += temp / count;
            }
        }
    }
    
    // 计算最终期望
    double res = 0;
    for (int i = 0; i < n; i++) {
        res += dp[k][i];
    }
    return res / n;
}

int main() {
    int n, m, k;
    while (cin >> n >> m >> k) {
        // 读入景点信息
        vector<Site> sites(n);
        for (int i = 0; i < n; i++) {
            cin >> sites[i].m >> sites[i].v[0] >> sites[i].v[1];
        }
        
        // 读入路径信息
        vector<vector<Path>> paths(n);
        for (int i = 0; i < m; i++) {
            int x, y, t;
            cin >> x >> y >> t;
            x--; y--;
            paths[x].push_back({y, t});
            paths[y].push_back({x, t});
        }
        
        // 计算两人的期望愉悦度
        double res1 = getExpectation(sites, paths, k, 0);
        double res2 = getExpectation(sites, paths, k, 1);
        
        cout << fixed << setprecision(5) << res1 << " " << res2 << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    static class Site {
        int m;
        double[] v = new double[2];
    }
    
    static class Path {
        int d, t;
        Path(int d, int t) {
            this.d = d;
            this.t = t;
        }
    }
    
    static double getExpectation(Site[] sites, List<Path>[] paths, int k, int p) {
        int n = sites.length;
        double[][] dp = new double[k + 1][n];
        
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                double temp = 0;
                int count = 0;
                
                if (i >= sites[j].m) {
                    dp[i][j] += sites[j].v[p];
                }
                
                for (Path path : paths[j]) {
                    if (i >= (path.t + sites[j].m + sites[path.d].m)) {
                        temp += dp[i - path.t - sites[j].m][path.d];
                        count++;
                    }
                }
                
                if (count > 0) {
                    dp[i][j] += temp / count;
                }
            }
        }
        
        double res = 0;
        for (int i = 0; i < n; i++) {
            res += dp[k][i];
        }
        return res / n;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            
            Site[] sites = new Site[n];
            for (int i = 0; i < n; i++) {
                sites[i] = new Site();
                sites[i].m = sc.nextInt();
                sites[i].v[0] = sc.nextDouble();
                sites[i].v[1] = sc.nextDouble();
            }
            
            @SuppressWarnings("unchecked")
            List<Path>[] paths = new List[n];
            for (int i = 0; i < n; i++) {
                paths[i] = new ArrayList<>();
            }
            
            for (int i = 0; i < m; i++) {
                int x = sc.nextInt() - 1;
                int y = sc.nextInt() - 1;
                int t = sc.nextInt();
                paths[x].add(new Path(y, t));
                paths[y].add(new Path(x, t));
            }
            
            double res1 = getExpectation(sites, paths, k, 0);
            double res2 = getExpectation(sites, paths, k, 1);
            
            System.out.printf("%.5f %.5f%n", res1, res2);
        }
        sc.close();
    }
}

class Site:
    def __init__(self):
        self.m = 0
        self.v = [0, 0]

class Path:
    def __init__(self, d, t):
        self.d = d
        self.t = t

def get_expectation(sites, paths, k, p):
    n = len(sites)
    dp = [[0] * n for _ in range(k + 1)]
    
    for i in range(1, k + 1):
        for j in range(n):
            temp = 0
            count = 0
            
            if i >= sites[j].m:
                dp[i][j] += sites[j].v[p]
            
            for path in paths[j]:
                if i >= (path.t + sites[j].m + sites[path.d].m):
                    temp += dp[i - path.t - sites[j].m][path.d]
                    count += 1
            
            if count:
                dp[i][j] += temp / count
    
    return sum(dp[k]) / n

def main():
    while True:
        try:
            n, m, k = map(int, input().split())
            
            sites = [Site() for _ in range(n)]
            for i in range(n):
                m_i, v1, v2 = map(float, input().split())
                sites[i].m = int(m_i)
                sites[i].v = [v1, v2]
            
            paths = [[] for _ in range(n)]
            for _ in range(m):
                x, y, t = map(int, input().split())
                x -= 1
                y -= 1
                paths[x].append(Path(y, t))
                paths[y].append(Path(x, t))
            
            res1 = get_expectation(sites, paths, k, 0)
            res2 = get_expectation(sites, paths, k, 1)
            
            print(f"{res1:.5f} {res2:.5f}")
            
        except EOFError:
            break

if __name__ == "__main__":
    main()