# 逛校园## 题目背景MRC 喜欢逛校园。## 题目描述MRC 在高三学习紧张的时候喜欢通过逛校园来释放压力。但是课间的时光总是短暂的MRC没办法逛太久。校园有很多标志性的建筑可以认为校园里的这些建筑和建筑之间的道路形成了一张 $n$ 个点 $m$ 条边的有向图第 $i$ 条边的长度为 $w_i$。MRC 现在手中有一张校园地图他希望找到最短的环你能帮帮他吗？## 输入格式第一行输入一个正整数

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MOD = 998244353;

struct Edge {
    int from, to, weight;
    Edge(int f, int t, int w): from(f), to(t), weight(w) {}
};

pair<int, int> shortestCycle(vector<vector<Edge>>& graph, int n) {
    vector<int> dist(n + 1, INT_MAX);
    vector<int> num(n + 1, 0);
    vector<int> inQueue(n + 1, 0);
    vector<int> inPath(n + 1, 0);
    queue<int> q;
    
    for (int i = 1; i <= n; i++) {
        dist[i] = 0;
        q.push(i);
        inQueue[i] = 1;
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = 0;
        
        for (Edge& e : graph[u]) {
            int v = e.to;
            int w = e.weight;
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                num[v] = num[u];
                
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = 1;
                    
                    if (++inPath[v] > n) {
                        return make_pair(-1, -1);
                    }
                }
            } else if (dist[u] + w == dist[v]) {
                num[v] = (num[v] + num[u]) % MOD;
            }
        }
    }
    
    int minLen = INT_MAX;
    int count = 0;
    
    for (int i = 1; i <= n; i++) {
        for (Edge& e : graph[i]) {
            int u = i;
            int v = e.to;
            int w = e.weight;
            
            if (dist[u] + w == dist[v]) {
                int len = dist[u] + dist[v] + w;
                
                if (len < minLen) {
                    minLen = len;
                    count = num[u] * num[v] % MOD;
                } else if (len == minLen) {
                    count = (count + num[u] * num[v]) % MOD;
                }
            }
        }
    }
    
    if (minLen == INT_MAX) {
        return make_pair(-1, -1);
    }
    
    return make_pair(minLen, count);
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int n, m;
        cin >> n >> m;
        
        vector<vector<Edge>> graph(n + 1);
        
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            
            graph[u].push_back(Edge(u, v, w));
        }
        
        pair<int, int> ans = shortestCycle(graph, n);
        cout << ans.first << " " << ans.second << endl;
    }
    
    return 0;
}
``