提出 #461331

---

ソースコード 拡げる

#include <bits/stdc++.h>

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>



#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define iter(a) __typeof(a.begin())
#define FOR(it,a) for(iter(a)it=a.begin();it!=a.end();++it)
#define F first
#define S second
#define SZ(a) (int)((a).size())
#define sz(a) SZ(a)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).begin(),(a).end()
using namespace std;

typedef long long ll;
typedef pair<int,int> PI;
typedef unsigned long long ull;

#ifdef ONLINE_JUDGE
#define PR(...) (void(0))
#else
#define PR(...) do{cerr << "line : " << __LINE__ << ", " << endl; pr(#__VA_ARGS__, __VA_ARGS__);}while(0)
template<class T>
void pr(const string& name, T t){
  cerr << name << ": " << t << endl;
}
template<typename T, typename ... Types>
void pr(const string& names, T t, Types ... rest) {
  auto p = names.find(',');
  cerr << names.substr(0, p) << ": " << t << ", ";
  pr(string(names, p + 1), rest ...);
}
#endif

template<class T,class U> ostream& operator<< (ostream& o, const pair<T,U>& v){return o << "(" << v.F << ", " << v.S << ")";}
template<class T> ostream& operator<< (ostream& o, const vector<T>& v){o << "{";rep(i,SZ(v)) o << (i?", ":"") << v[i];return o << "}";}
template<class T,class U> ostream& operator<< (ostream& o, const map<T,U>& v){o << "{";for(const auto& e : v) o << e << ", ";return o << "}";}
template<class T> ostream& operator<< (ostream& o, const set<T>& v){o << "{";for(const auto& e : v) o << e << ", ";return o << "}";}
template<class T> string to_s(const T& v){ostringstream is;is << v;return is.str();}

const int dx[]={0,1,0,-1,1,1,-1,-1,0};
const int dy[]={1,0,-1,0,-1,1,1,-1,0};

#define endl '\n'

int ok[100][100];
pair<int, string> ans;
int s, g;
vector<string> in;

void dfs(int de, int cv, string a, int re){
  if(de > ans.F) return;
  re |= cv == g;
  if(re && ok[cv][s]){
    ans = min(ans, mp(de, a));
  }
  
  rep(i, 10){
    if(ok[cv][i]){
      ok[cv][i] = ok[i][cv] = 0;
      dfs(de + 1, i, a + in[i], re);
      ok[cv][i] = ok[i][cv] = 1;
    }
  }
}

int main(int argc, char *argv[])
{
  int n;
  cin >> n;

  in.resize(n);
  rep(i, n) cin >> in[i];
  int m;
  cin >> m;
  vector<pair<string, string> > ed(m);
  rep(i, m) cin >> ed[i].F >> ed[i].S;
  
  rep(i, m){
    int a = find(ALL(in), ed[i].F) - in.begin();
    int b = find(ALL(in), ed[i].S) - in.begin();
    //PR(a, b);
    ok[a][b] = ok[b][a] = 1;
  }
    


  {
    string t;
    cin >> t;
    s = find(ALL(in), t) - in.begin();
  }

  {
    string t;
    cin >> t;
    g = find(ALL(in), t) - in.begin();
  }
  ans.F = 1000;
  dfs(0, s, in[s], 0);
  
  cout << ans.S << endl;
  return 0;
  
  set<pair<pair<int, string>, pair<int,int> > > q;
  

  q.insert(mp(mp(0,in[s]), mp(s,0)));
  
  map<pair<int, int>, pair<int, string> > vis;


  
  while(!q.empty()){
    auto cv = *q.begin();
    q.erase(cv);
    cv.S.S |= cv.S.F == g;
    if(vis.count(cv.S) && vis[cv.S] <= cv.F) continue;
    PR(cv);
    vis[cv.S] = cv.F;
    if(cv.S.S && ok[cv.S.F][s]){
      ans = min(ans, mp(cv.F.F + 1, cv.F.S));
    }
    
    rep(i, n){
      // PR(ok[cv.S.F][i]);
      if(ok[cv.S.F][i])
        q.insert(mp(mp(cv.F.F + 1, cv.F.S + in[i]),mp(i,cv.S.S)));
    }
  }
  
  cout << ans.S << endl;
}

提出情報

ジャッジ結果