时空穿越PTA使用C++或者C语言解答

Question

时空穿越
有N（1≤N≤500）个城市，他们的编号是1∼N，t
ij
​
表示城市i和城市j之间可在t
ij
​
秒内互达，即城市之间的道路是双向的，且两个城市之间可能有多条道路，总共的道路数不超过3000条。

有些城市之间有神秘的单向道路，这条神秘道路可以把你从城市i带回城市j，且可使时间回流m
i]
​
秒。

所以，你可能在某地遇到之前的你。

例如，城市1到城市2有普通双向道路可使得在2秒内互达，同时城市2到城市1有神秘道路，可把你带回且时间回流3秒。于是，你从1出发，按照1->2的普通道路和2->1的神秘道路行走，在城市1看到了出发前的自己。

请编写程序，计算能否遇到之前的你。

输入格式:
第一行有一个整数T，表示有T(1≤10)组数据。

接下来是对每组数据的描述：（以下第i行是相对组内数据而言）

第1行有3个整数N,M,S，分别表示有N个城市和它们之间的M条普通道路和S条神秘道路。(1≤N≤500,0≤M,S≤3000)

接下来M行，每行有3个整数x,y,t，分别表示城市x和y的普通道路，可在t秒内互达。0≤t≤10000

再接下来S行，每行有3个整数x,y,t，分别表示城市x到城市y的单向神秘道路，时间回流t秒。0≤t≤10000

输出格式:
若能找到一个出发点，按照题意能遇到之前的自己，输出YES，否则输出NO。

每组数据对应一行输出。

输入样例:
2
2 1 1
1 2 2
2 1 3
2 1 1
1 2 3
2 1 2
输出样例:
YES
NO
代码长度限制
16 KB
时间限制
800 ms
内存限制

Answer 1

以下是使用C++编写的解答示例：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int INF = INT_MAX;

struct Edge {
    int to;
    int time;
    bool isMysterious;
};

bool canMeetAgain(int start, int N, const vector<vector<Edge>>& graph) {
    vector<int> dist(N + 1, INF);
    vector<bool> visited(N + 1, false);
    dist[start] = 0;
    
    queue<int> q;
    q.push(start);
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        visited[curr] = false;
        
        for (const Edge& e : graph[curr]) {
            int next = e.to;
            int time = e.time;
            bool isMysterious = e.isMysterious;
            
            int newDist = dist[curr] + time;
            if (isMysterious) {
                newDist -= time; // 时间回流
            }
            
            if (newDist < dist[next]) {
                dist[next] = newDist;
                
                if (!visited[next]) {
                    q.push(next);
                    visited[next] = true;
                }
            }
        }
    }
    
    // 检查是否存在负环
    for (int i = 1; i <= N; i++) {
        for (const Edge& e : graph[i]) {
            int next = e.to;
            int time = e.time;
            bool isMysterious = e.isMysterious;
            
            int newDist = dist[i] + time;
            if (isMysterious) {
                newDist -= time; // 时间回流
            }
            
            if (newDist < dist[next]) {
                return true; // 存在负环，可以遇到之前的自己
            }
        }
    }
    
    return false;
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int N, M, S;
        cin >> N >> M >> S;
        
        vector<vector<Edge>> graph(N + 1);
        
        // 读取普通道路
        for (int i = 0; i < M; i++) {
            int x, y, t;
            cin >> x >> y >> t;
            graph[x].push_back({y, t, false});
            graph[y].push_back({x, t, false});
        }
        
        // 读取神秘道路
        for (int i = 0; i < S; i++) {
            int x, y, t;
            cin >> x >> y >> t;
            graph[x].push_back({y, t, true});
        }
        
        // 从每个城市出发，判断是否能遇到之前的自己
        bool found = false;
        for (int i = 1; i <= N; i++) {
            if (canMeetAgain(i, N, graph)) {
                found = true;
                break;
            }
        }
        
        if (found) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

该解答使用了图的广度优先搜索（BFS）算法，并使用了松弛操作来计算最短路径。首先，根据输入构建城市之间的图，其中每个边表示一条道路，包括普通道路和神秘道路。然后，从每个城市出发进行搜索，判断是否存在负环，如果存在负环，则可以遇到之前的自己。最后，根据搜索结果输出相应的答案。

请注意，该示例代码仅提供了一种解决该问题的思路和实现方式，实际实现中可能需要根据具体要求进行适当的修改和优化。