제출 #101489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101489		dwsc	007 (CEOI14_007)	C++14	0 / 100	796 ms	27284 KiB

007

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> adj[m];
    int s,d,a,b;
    cin >> s >> d >> a >> b;
    s--;
    d--;
    a--;
    b--;
    for (int i = 0; i < m; i++){
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    queue<int> q;
    int p1[n],p2[n];
    int dist1[n],dist2[n];
    memset(dist1,-1,sizeof(dist1));
    memset(dist2,-1,sizeof(dist2));
    dist1[s] = 0;
    dist2[d] = 0;
    q.push(s);
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i];
            if (dist1[v] == -1){
                dist1[v] = dist1[u]+1;
                q.push(v);
                p1[v] = u;
            }
        }
    }
    q.push(d);
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i];
            if (dist2[v] == -1){
                dist2[v] = dist2[u]+1;
                q.push(v);
                p2[v] = u;
            }

        }
    }
   // cout << dist1[a] << " " << dist1[b] << "\n";
   // cout << dist2[a] << " " << dist2[b] << "\n";
    if (dist2[a] < dist1[a] && dist2[b] < dist1[b]) cout << -1;
    else{
        if (dist1[a] > dist1[b]){
            swap(dist1[a],dist1[b]);
            swap(dist2[a],dist2[b]);
        }
        if (dist1[a] == dist1[b]){
            if (dist2[a] == dist2[b]){
                int fin1s = a,fin2s = b;
                int fin1d = a,fin2d = b;
                int num1 = 0,num2 = 0;
                while (fin1s != fin2s){
                    for (int i = 0; i < adj[fin1s].size(); i++){
                        if (dist1[adj[fin1s][i]]+1 == dist1[fin1s]){
                            fin1s = adj[fin1s][i];
                            break;
                        }
                    }
                    for (int i = 0; i < adj[fin2s].size(); i++){
                        if (dist1[adj[fin2s][i]]+1 == dist1[fin2s]){
                            fin2s = adj[fin2s][i];
                            break;
                        }
                    }
                    num1++;
                }
                while (fin1d != fin2d){
                     for (int i = 0; i < adj[fin1d].size(); i++){
                        if (dist2[adj[fin1d][i]]+1 == dist2[fin1d]){
                            fin1d = adj[fin1d][i];
                            break;
                        }
                    }
                    for (int i = 0; i < adj[fin2d].size(); i++){
                        if (dist2[adj[fin2d][i]]+1 == dist2[fin2d]){
                            fin2d = adj[fin2d][i];
                            break;
                        }
                    }
                    num2++;
                }
                cout << dist2[a]-dist1[a]-(num2<num1);
            }
            else if (dist2[a]+1 == dist2[b]) cout << dist2[a] - dist1[a];
            else cout << dist2[b] - dist1[b];
        }
        else if (dist1[a]+1 == dist1[b]){
            if (dist2[a] == dist2[b]) cout << dist2[b] - dist1[b];
            else if (dist2[a] +1 == dist2[b]) cout << dist2[a] - dist1[a];
            else cout << dist2[b] - dist1[b];
        }
    }
}/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/

컴파일 시 표준 에러 (stderr) 메시지

007.cpp: In function 'int main()':
007.cpp:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:69:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 0; i < adj[fin1s].size(); i++){
                                     ~~^~~~~~~~~~~~~~~~~~~
007.cpp:75:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 0; i < adj[fin2s].size(); i++){
                                     ~~^~~~~~~~~~~~~~~~~~~
007.cpp:84:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                      for (int i = 0; i < adj[fin1d].size(); i++){
                                      ~~^~~~~~~~~~~~~~~~~~~
007.cpp:90:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 0; i < adj[fin2d].size(); i++){
                                     ~~^~~~~~~~~~~~~~~~~~~
007.cpp:22:9: warning: variable 'p1' set but not used [-Wunused-but-set-variable]
     int p1[n],p2[n];
         ^~
007.cpp:22:15: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
     int p1[n],p2[n];
               ^~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70