首页 > 代码库 > Sicily 1308. Dependencies among J 解题报告

Sicily 1308. Dependencies among J 解题报告

2024-07-15 05:31:40   215人阅读

题目：1308. Dependencies among J

 

 

思路：

　　比较简单的一道题，要知道m最早完成的时间，只需要找出所有需要在m之前完成的工作，将它们的完成时间加起来即可。这里使用vector的数组存储每个结点的邻接点，从结点m开始，依次宽度优先搜索m的每个邻接点...数组visited记录每个结点是否被访问过，遇到已经访问过的结点直接跳过。

　　读取的时候一开始没有找到解决办法，要读取一行的数字，并且要判断是否换行，可以首先读取第一个数即完成时间，然后用getchar读取一个字符，如果是‘\n‘则是换行，否则继续读下一个数。

 

 

代码：

 1 #include <iostream> 2 #include <vector> 3 #include <queue> 4 #include <stdio.h> 5 using namespace std; 6  7 const int MAX = 10001; 8  9 int main() {10     int n, m;11     int times[MAX];12     bool visited[MAX];13     while (scanf("%d", &n) && n != 0) {14         int result = 0;15         scanf("%d", &m);16         vector<int> v[n + 1];17         queue<int> q;18         for (int i = 1; i <= n; ++i) {//读取n行数据19             scanf("%d", &times[i]);20             char c; //读取空格或换行符21             int temp;22             while (scanf("%c", &c) && c != ‘\n‘) {23                 scanf("%d", &temp);24                 v[i].push_back(temp);25             }26             visited[i] = false;27         }28         q.push(m);29         visited[m] = true;30         result += times[m];31         //往回遍历完成m之前需要完成的任务,用队列实现宽度优先搜索32         while (!q.empty()) {33             int temp = q.front();34             q.pop();35             vector<int>::iterator it;36             for (it = v[temp].begin(); it != v[temp].end(); it++) {37                 if (!visited[*it]) {38                     visited[*it] = true;39                     q.push(*it);40                     result += times[*it];41                 }42             }43         }44         cout << result << endl;45     }46     return 0;47 }

 


联系
我们