#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;
}