算法训练营day72
题目：117. 软件构建 (kamacoder.com)
#include<iostream>
#include<unordered_map>
#include<vector>
#include<queue>using namespace std;int main() {int n, m;cin >> n >> m;vector<int> indegree(n, 0);unordered_map<int, vector<int>> map;int s, t;while(m--) {cin >> s >> t;indegree[t]++;map[s].push_back(t);}queue<int> qu;for(int i = 0;i < n;i++) {if(indegree[i] == 0) {qu.push(i);}}vector<int> result;while(!qu.empty()) {int cur = qu.front();qu.pop();result.push_back(cur);vector<int> files = map[cur];if(files.size()) {for(int i = 0;i < files.size();i++) {indegree[files[i]]--;if(indegree[files[i]] == 0) qu.push(files[i]);} }}if(result.size() == n) {for(int i = 0;i < n - 1;i++) {cout << result[i] << " ";}cout << result[n - 1] << endl;}else {cout << -1 << endl;}return 0;
}题目2：47. 参加科学大会（第六期模拟笔试） (kamacoder.com)
#include<bits/stdc++.h>using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));vector<bool> vistied(n + 1, false);vector<int> minDist(n + 1, INT_MAX);while(m--) {int s, e, v;cin >> s >> e >> v;grid[s][e] = v;}minDist[1] = 0;int cur = 1;for(int i = 1;i <= n;i++) {int minVal = INT_MAX;for(int v = 1;v <= n;v++) {if(!vistied[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}vistied[cur] = true;for(int j = 1;j <= n;j++) {if(!vistied[j] && grid[cur][j] != INT_MAX && minDist[cur] + grid[cur][j] < minDist[j]) {minDist[j] = minDist[cur] + grid[cur][j];}}}if(minDist[n] == INT_MAX) cout << -1 << endl;else cout << minDist[n] << endl;return 0;
}