test/aoj/0596.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 16:52:37+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596

Depends on

• graph/bfs.cpp
• tools/chminmax.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596

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

#define call_from_test
#include "../../graph/bfs.cpp"
#include "../../tools/chminmax.cpp"
#undef call_from_test

signed main(){
  int n,k;
  cin>>n>>k;

  vector<int> cs(n),rs(n);
  for(int i=0;i<n;i++) cin>>cs[i]>>rs[i];

  vector<vector<int> > G(n);
  for(int i=0;i<k;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }

  vector< vector<int> > di(n);
  for(int i=0;i<n;i++) di[i]=bfs(i,G);

  const int INF = 1e9;
  vector<int> dp(n,INF);
  vector<int> used(n,0);
  dp[0]=0;

  for(int i=0;i<n;i++){
    int u=-1;
    for(int j=0;j<n;j++){
      if(used[j]||dp[j]==INF) continue;
      if(u<0||dp[u]>dp[j]) u=j;
    }
    if(u<0) break;
    used[u]=1;
    for(int j=0;j<n;j++){
      if(di[u][j]>rs[u]) continue;
      chmin(dp[j],dp[u]+cs[u]);
    }
  }

  cout<<dp[n-1]<<endl;
  return 0;
}

#line 1 "test/aoj/0596.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0596

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

#define call_from_test
#line 1 "graph/bfs.cpp"

#line 3 "graph/bfs.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
vector<int> bfs(int s,vector< vector<int> > G){
  int n=G.size();
  vector<int> dp(n,-1);
  queue<int> que;
  dp[s]=0;
  que.emplace(s);
  while(!que.empty()){
    int v=que.front();que.pop();
    for(int u:G[v]){
      if(~dp[u]) continue;
      dp[u]=dp[v]+1;
      que.emplace(u);
    }
  }
  return dp;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "tools/chminmax.cpp"

#line 3 "tools/chminmax.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 9 "test/aoj/0596.test.cpp"
#undef call_from_test

signed main(){
  int n,k;
  cin>>n>>k;

  vector<int> cs(n),rs(n);
  for(int i=0;i<n;i++) cin>>cs[i]>>rs[i];

  vector<vector<int> > G(n);
  for(int i=0;i<k;i++){
    int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace_back(y);
    G[y].emplace_back(x);
  }

  vector< vector<int> > di(n);
  for(int i=0;i<n;i++) di[i]=bfs(i,G);

  const int INF = 1e9;
  vector<int> dp(n,INF);
  vector<int> used(n,0);
  dp[0]=0;

  for(int i=0;i<n;i++){
    int u=-1;
    for(int j=0;j<n;j++){
      if(used[j]||dp[j]==INF) continue;
      if(u<0||dp[u]>dp[j]) u=j;
    }
    if(u<0) break;
    used[u]=1;
    for(int j=0;j<n;j++){
      if(di[u][j]>rs[u]) continue;
      chmin(dp[j],dp[u]+cs[u]);
    }
  }

  cout<<dp[n-1]<<endl;
  return 0;
}

Back to top page