电子商务网站建设实训_广州冼村社区服务中心电话_关键词网站_应用商店下载安装

原题

#include <iostream>
#include <vector>
#include <queue>
#include <set>using namespace std;struct edge {int destination;int dist;edge(int destination_, int dist_) : destination(destination_), dist(dist_) {}
};vector<edge> graph[100];
vector<edge> reGraph[100];
vector<int> inDo(100, 0);
vector<int> outDo(100, 0);
vector<int> lessTime(100, 0);
vector<int> moreTime(100, 0x3fffffff);int main() {int n, m;cin >> n >> m;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;graph[u].emplace_back(v, w);reGraph[v].emplace_back(u, w);outDo[u]++;inDo[v]++;}queue<int> q;for (int i = 0; i < n; ++i) {if (inDo[i] == 0) {q.push(i);lessTime[i] = 0;}}while (!q.empty()) {int cur = q.front();q.pop();for (edge neighbor: graph[cur]) {inDo[neighbor.destination]--;lessTime[neighbor.destination] = max(lessTime[neighbor.destination], lessTime[cur] + neighbor.dist);if (inDo[neighbor.destination] == 0) {q.push(neighbor.destination);}}}int totalTime = 0;for (int i = 0; i < n; ++i) {if (inDo[i] != 0) {cout << "No" << endl;return 0;}totalTime = max(totalTime, lessTime[i]);}for (int i = 0; i < n; ++i) {if (outDo[i] == 0) {q.push(i);moreTime[i] = totalTime;}}while (!q.empty()) {int cur = q.front();q.pop();for (edge neighbor: reGraph[cur]) {outDo[neighbor.destination]--;moreTime[neighbor.destination] = min(moreTime[neighbor.destination], moreTime[cur] - neighbor.dist);if (outDo[neighbor.destination] == 0) {q.push(neighbor.destination);}}}set<pair<int, int>> s;for (int i = 0; i < n; ++i) {for (edge neighbor: graph[i]) {if (moreTime[neighbor.destination] - lessTime[i] - neighbor.dist == 0) {s.insert({i, neighbor.destination});}}
}//    for (int i = 0; i < n; ++i) {
//        if (lessTime[i] == 0 && moreTime[i] == 0) {
//            q.push(i);
//        }
//    }//    while (!q.empty()) {
//        auto cur = q.front();
//        q.pop();//        for (auto neighbor: graph[cur]) {
//            if (lessTime[neighbor.destination] == moreTime[neighbor.destination]) {
//                s.insert({cur, neighbor.destination});
//            q.push(neighbor.destination);
//            }
//        }
//    }cout << "Yes" << endl;for (auto p: s) {cout << p.first << " " << p.second << endl;}return 0;
}