Submission

[P-SSSSSSSS][P-SSSSSSSSSSSSSS]

Score: 0

User: MiyaZaki1072

Problemset: 03.Looper

Language: cpp

Time: 0.048 second

Submitted On: 2025-04-28 19:50:22

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int>adj[1010];
//dis[st][i] + (k-1)*(dis[i][j] + dis[j][i]); go st to i and then try go from i j j i to make a loop
ll dis[1010][1010],ans;
int n,m,st,k,idx;
queue<int>qu;
void bfs(int st){
    qu.push(st);
    dis[st][st]=0;
    while(qu.size()){
        int u = qu.front();qu.pop();
        for(int v:adj[u]){
            if(dis[st][v] > dis[st][u] + 1){
                dis[st][v] = dis[st][u] + 1;
                qu.push(v);
            }
        }
    }
}
void solve(){
    memset(dis,0x3f,sizeof dis);
    ans=LLONG_MAX;
    cin>>n>>m>>k>>st;
    for(int i=1;i<=n;i++)adj[i].clear();
    while(m--){
        int u,v;cin>>u>>v;
        adj[u].push_back(v);
    }
    for(int i=1;i<=n;i++)bfs(i);//N^2;
    for(int i=1;i<=n;i++){
        if(dis[st][i] > 1e9)continue;
        for(int j=1;j<=n;j++){
            if(i==j || dis[i][j] > 1e9 || dis[j][i] > 1e9)continue;
            ll rn = dis[st][i] + (k-1) * (dis[i][j] + dis[j][i]);
            if(rn < ans){
                ans = rn;
                idx = i;
            }
            else if(rn == ans)idx=min(idx,i);
        }
    }
    if(ans > 1e9)cout<<-1<<'\n';
    else cout<<ans<<" "<<idx<<"\n";
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int TC;cin>>TC;
    while(TC--)solve();
}