题目分析

这道题目要求我们找出所有可能在规定时间内到达谷仓的嫌疑牛。具体来说：

1. 农场结构：农场由F个田地（编号1到F）和P条双向路径组成，每条路径有特定的穿越时间。
2. 犯罪时间：卫星在犯罪发生前M秒拍摄了农场照片，记录了所有牛的位置。
3. 目标：确定哪些牛可以在不超过M秒的时间内从它们所在的位置到达谷仓（田地1）。

解题思路

1. 图建模：

   • 将农场建模为一个无向图，田地作为节点，路径作为边，路径时间作为边的权重。

2. 最短路径计算：

   • 使用Dijkstra算法计算从谷仓（田地1）到所有其他田地的最短时间。因为路径是双向的，所以从谷仓到其他田地的时间等于从其他田地到谷仓的时间。

3. 筛选嫌疑牛：

   • 对于每头牛，检查其所在田地到谷仓的最短时间是否不超过M秒。如果是，则该牛有作案嫌疑。

代码实现步骤

1. 输入处理：

   • 读取农场的基本信息（田地数量F，路径数量P，牛的数量C，时间限制M）。
   • 读取所有路径信息，构建邻接矩阵表示图。

2. 最短路径计算：

   • 初始化距离数组dis，dis[1] = 0（谷仓到自身的距离为0），其他初始为无穷大。
   • 使用Dijkstra算法计算从田地1到所有其他田地的最短时间。

3. 嫌疑牛筛选：

   • 读取每头牛的位置，检查该位置到谷仓的最短时间是否≤M。
   • 收集所有满足条件的牛的编号。

4. 输出结果：

   • 输出嫌疑牛的数量，然后按升序输出这些牛的编号。

复杂度分析

• 时间复杂度：

  • Dijkstra算法使用邻接矩阵实现，复杂度为O(F^2)，其中F是田地数量（最多500）。
  • 筛选牛的过程是O(C)，其中C是牛的数量（最多100）。
  • 总体复杂度为O(F^2 + C)，在题目限制下是可接受的。

• 空间复杂度：

  • 邻接矩阵需要O(F^2)空间（500x500=250,000）。
  • 距离数组和访问标记数组各需要O(F)空间。
  • 结果数组需要O(C)空间。
  • 总体空间复杂度为O(F^2 + C)，也在合理范围内。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 500
#define INF 0x7f7f7f7f
using namespace std;

int f, p, c, m;
int mp[MAX+5][MAX+5];  // 邻接矩阵存储图
int dis[MAX+5];        // 存储从谷仓到各田地的最短时间
bool vis[MAX+5];       // 标记是否已确定最短路径
int ans[100+5];        // 存储嫌疑牛的编号

void Init() {
    // 初始化邻接矩阵
    for(int i = 0; i < MAX+5; i++)
        for(int j = 0; j < MAX+5; j++)
            mp[i][j] = INF;
    
    memset(vis, false, sizeof(vis));
    memset(ans, 0, sizeof(ans));
    
    // 读取输入
    scanf("%d %d %d %d", &f, &p, &c, &m);
    
    // 读取路径信息
    for(int i = 0; i < p; i++) {
        int s, e, len;
        scanf("%d %d %d", &s, &e, &len);
        if(mp[s][e] > len) {
            mp[s][e] = len;
            mp[e][s] = len;  // 无向图
        }
    }
}

void Dijkstra() {
    // 初始化距离数组
    dis[1] = 0;          // 谷仓到自身距离为0
    for(int i = 2; i <= f; i++)
        dis[i] = INF;
    
    // Dijkstra算法主循环
    for(int i = 1; i < f; i++) {
        int tmp = 0, min_dis = INF;
        
        // 找到当前未访问的距离最小的节点
        for(int j = 1; j <= f; j++) {
            if(!vis[j] && dis[j] < min_dis) {
                min_dis = dis[j];
                tmp = j;
            }
        }
        
        vis[tmp] = true;  // 标记为已访问
        
        // 更新邻接节点的距离
        for(int j = 1; j <= f; j++) {
            if(mp[tmp][j] != INF && dis[j] > dis[tmp] + mp[tmp][j]) {
                dis[j] = dis[tmp] + mp[tmp][j];
            }
        }
    }
}

int main() {
    Init();          // 初始化并读取输入
    Dijkstra();      // 计算最短路径
    
    int num = 0;     // 嫌疑牛计数
    
    // 检查每头牛的位置
    for(int i = 1; i <= c; i++) {
        int cow_loc;
        scanf("%d", &cow_loc);
        if(dis[cow_loc] <= m) {
            ans[num++] = i;  // 记录嫌疑牛编号
        }
    }
    
    // 输出结果
    printf("%d\n", num);
    for(int i = 0; i < num; i++) {
        printf("%d\n", ans[i]);
    }
    
    return 0;
}