156762025-02-21 17:51:37999Fertőzési sorozat (50 pont)cpp17Hibás válasz 42/50354ms2584 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e12;

signed main() {
    int n,m,k;cin>>n>>m>>k;
    vector<vector<int>> fw(n, vector<int>(n,INF));
    vector<int> v(k);
    for(int &i:v){cin>>i;i--;}
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        fw[--a][--b]=1;
        fw[b][a]=1;
    }
    for(int i = 0;i<n;i++)fw[i][i]=0;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            for(int k = 0;k<n;k++){
                fw[k][j]=min(fw[k][j],fw[i][k]+fw[i][j]);
            }
        }
    }//for(int i = 0;i<n;i++){for(int j = 0;j<n;j++)cerr<<fw[i][j]<<' ';cerr<<endl;}
    vector<int> ans;
    for(int i = 0;i<n;i++){
        bool boo=true;
        for(int j=0;j<k;j++){
            int l=v[j];
            if(j==0)continue;
            if(!(fw[i][l]-fw[i][v[j-1]]<=1&&fw[i][l]-fw[i][v[j-1]]>=0)){
                boo=false;
                break;
            }
        }
        if(boo){
            ans.push_back(i);
        }
    }
    cout<<ans.size()<<endl;
    for(int i:ans)cout<<i+1<<' ';
    cout<<endl;
}
 
RészfeladatÖsszpontTesztVerdiktIdőMemória
base42/50
1Elfogadva0/01ms508 KiB
2Elfogadva0/01ms508 KiB
3Elfogadva0/030ms896 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/23ms476 KiB
6Elfogadva2/230ms896 KiB
7Elfogadva2/229ms1012 KiB
8Elfogadva2/230ms904 KiB
9Elfogadva2/230ms824 KiB
10Elfogadva2/2352ms2380 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/2352ms2380 KiB
13Elfogadva2/2354ms2540 KiB
14Elfogadva2/2351ms2376 KiB
15Elfogadva2/2349ms2372 KiB
16Elfogadva2/2352ms2356 KiB
17Elfogadva2/2354ms2356 KiB
18Elfogadva1/1352ms2380 KiB
19Elfogadva1/1349ms2372 KiB
20Elfogadva1/1349ms2308 KiB
21Elfogadva1/1349ms2376 KiB
22Elfogadva1/1352ms2376 KiB
23Elfogadva1/1349ms2248 KiB
24Hibás válasz0/1351ms2376 KiB
25Elfogadva1/1351ms2380 KiB
26Elfogadva1/1347ms2384 KiB
27Hibás válasz0/1349ms2356 KiB
28Hibás válasz0/1349ms2376 KiB
29Elfogadva1/1349ms2356 KiB
30Hibás válasz0/1352ms2540 KiB
31Hibás válasz0/1347ms2584 KiB
32Elfogadva1/1354ms2356 KiB
33Elfogadva1/1352ms2376 KiB
34Hibás válasz0/1351ms2356 KiB
35Hibás válasz0/1349ms2376 KiB
36Hibás válasz0/1347ms2372 KiB
37Elfogadva1/1349ms2376 KiB
38Elfogadva1/1352ms2356 KiB
39Elfogadva1/1352ms2356 KiB
40Elfogadva1/1351ms2540 KiB