Submission

[P-SSSSSSSS][PTSSSSSSSSSSSSSS]

Score: 0

User: pxsit

Problemset: 03.Looper

Language: cpp

Time: 1.089 second

Submitted On: 2025-03-31 07:58:18

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long

bool valid = false;

int n, m, k, s, last;
int city, mn = INT_MAX;

void dfs(int u, int c, vector<vector<int>> &adj, vector<bool> vis, vector<ll> &dis, set<int> traveled){
    // cout << u << endl;
    if(vis[u]){
        // cout << "travel: ";
        // for(auto i: traveled) cout << i << ' '; cout << endl;
        valid = true;
        if(mn>(c-dis[u])*(k-1)+dis[u]){
            mn = (c-dis[u])*(k-1)+dis[u];
            city = u;
        }else if(mn==(c-dis[u])*(k-1)+dis[u]){
            city = min(city,u);
        }return;
    }
    vis[u] = true;
    for(auto v: adj[u]){
        dis[v] = min(dis[v],dis[u]+1);
        traveled.insert(u);
        dfs(v,c+1,adj,vis,dis,traveled);
    }
}

void solve(){
    mn = INT_MAX;
    valid = false;
    cin >> n >> m >> k >> s;
    vector<vector<int>> adj(n+1);
    for(int i = 1, u, v; i <= m; i++){
        cin >> u >> v;
        adj[u].emplace_back(v);
    }
    vector<bool> vis(n+1,0);
    vector<ll> dis(n+1,1e18);
    set<int> traveled;
    dis[s] = 0;
    dfs(s,0,adj,vis,dis,traveled);
    // for(int i = 1; i <= n; i++) cout << dis[i] << ' '; cout << endl;
    // for(int i = 1; i <= n; i++) cout << vis[i] << ' '; cout << endl;
    if(!valid) cout << -1 << endl;
    else cout << mn << ' ' << city << endl;
    return;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}