This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// 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; }