結果

問題 No.583 鉄道同好会
コンテスト
ユーザー Gurren47881
提出日時 2017-10-27 23:15:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 1,541 bytes
コンパイル時間 733 ms
コンパイル使用メモリ 73,856 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-11-21 23:14:13
合計ジャッジ時間 1,759 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:69:11: warning: 'first' may be used uninitialized [-Wmaybe-uninitialized]
   69 |   dijkstra(first);
      |   ~~~~~~~~^~~~~~~
main.cpp:50:7: note: 'first' was declared here
   50 |   int first;
      |       ^~~~~

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define REP(i,n) for(int i = 0;i < (n);i++)
#define pb push_back
typedef long long ll;

#define MV 100000
#define INF 1e9

struct edge{int to,cost; };
vector <edge> G[MV];
bool used[MV];
int d[MV+1];

int V,E;

void dijkstra(int first){
  fill(d,d+MV,INF);
  fill(used,used+MV,false);
  d[first] = 0;

  for(int i = 0;i < V;i++){
    int now = MV;

    for(int j = 0;j < V;j++){
      if(used[j] == false && d[now] > d[j]){
	now = j;
      }
    }
    // cout << now << endl; デバッグ用、条件1が正しく動作しているかを確かめられる
    used[now] = true;
    for(int j = 0;j < G[now].size();j++){
      edge e = G[now][j];
      d[e.to] = min(d[e.to] , d[now]+e.cost);
    }
    /*for(int j = 0;j < V;j++)
      cout << d[j] << "   ";
      cout << endl;　
デバッグ用で、各点の更新後の最短経路が見れる
*/
    
  }
}


int main(){
  d[MV] = INF+10;
  int first;
  
  cin >> V >> E;
  int a[V] = {0};
  for(int i = 0;i < E;i++){
    int f,t;
    edge e;
    cin >> f >> e.to;
    a[f]++;
    a[e.to]++;
    first = f;
    e.cost = 1;
    G[f].push_back(e);
    t = e.to;
    e.to = f;
      G[t].push_back(e);
  }

  
  dijkstra(first);
  int r = 0,sum = 0,ki = 0;
  REP(i,V){
    if(d[i] == INF)
      r++;
    if(a[i] == 0)
      sum++;
    if(a[i]%2 == 1)
      ki++;
  }
  if(r == sum){
    if(ki <= 2)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
  else{
    cout << "NO" << endl;
  }
  
}
0