AOJ 2608 Minus One
#include<bits/stdc++.h> #define fi first #define se second #define show(x) cerr<<#x<<"="<<x<<"\n" typedef long long ll; using namespace std; //const ll MOD=(ll)1e9+7; const int inf=(int)1e9; const int dy[]={1,0,-1}; const int dx[]={1,0,-1}; int n,m,h,w; int s,t; //Shortest_Path //グラフの最短距離を求めるアルゴリズムを3種類持っているクラスです class shortest_path{ public: //dijkstra法とBellman_Ford法を使うときは、このコンストラクタを使ってください explicit shortest_path(int n):vertex(n),INF((ll)1e14){ v1.resize(static_cast<unsigned long>(vertex)); } //Warshall_Floyd法を使うときは、こちらのコンストラクタを使ってください shortest_path(int n,ll inf):vertex(n),INF(inf){ v2.resize(static_cast<unsigned long>(vertex)); for(int i=0;i<vertex;i++)v2[i].resize(static_cast<unsigned long>(vertex)); for(int i=0;i<vertex;i++){ for(int j=0;j<vertex;j++){ v2[i][j]=INF; } } for(int i=0;i<vertex;i++)v2[i][i]=0; } //dijkstra法とBellman_Ford法専用のadd_edge(int from,int to,ll cost)です //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost) void add_edge(int from,int to,ll cost){ v1[from].push_back({to,cost}); } //Warshall_Floyd法専用のadd_edge(int from,int to,ll cost)です //コストcostの頂点fromから頂点toへの有向辺を追加するときadd_edge(int from,int to,ll cost) void add_edge_(int from,int to,ll cost){//warshall_floyd v2[from][to]=cost; } //Dijkstra法です //各頂点への距離が格納されたvector<ll>が求まります //負のコストの辺がある場合は使えません //start地点の頂点番号を引数に入れてください vector<ll> dijkstra(unsigned int start){ vector<ll> d(static_cast<unsigned long>(vertex),INF); priority_queue<pair<ll,int> > q; d[start]=0; q.push({0,start}); while(!q.empty()){ int now=q.top().se; ll now_cost=-q.top().fi; q.pop(); if(d[now]<now_cost)continue; for (auto &i : v1[now]) { if(d[i.fi]>now_cost+ i.se){ d[i.fi]=now_cost+ i.se; q.push({-d[i.fi], i.fi}); } } } return d; } //Warshall_Floyd法です //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます //閉路があるとき、返り値はtrueです tuple<vector<vector<ll> >,bool> warshall_floyd(){ for(int k=0;k<vertex;k++){ for(int i=0;i<vertex;i++){ if(v2[i][k]==INF)continue; for(int j=0;j<vertex;j++){ if(v2[k][j]==INF)continue; v2[i][j]=min(v2[i][j],v2[i][k]+v2[k][j]); } } } bool is_negative_cycle=false; for(int i=0;i<vertex;i++){ if(v2[i][i]<0)is_negative_cycle=true; } return make_tuple(v2,is_negative_cycle); } //Bellman_Ford法です //各頂点への距離が格納されたvector<ll>と閉路があるかどうかの情報の2つのtupleが返されます //閉路があるとき、返り値はtrueです //start地点の頂点番号を引数に入れてください tuple<vector<ll>,bool> bellman_ford(int start){ vector<ll> d(static_cast<unsigned long>(vertex),INF); d[start]=0; bool is_negative_cycle=false; for(int i=0;i<vertex;i++){ bool update= false; for(int j=0;j<vertex;j++){ if(d[j]==INF)continue; for(int k=0;k<(int)v1[j].size();k++){ if(d[v1[j][k].fi]>d[j]+v1[j][k].se){ d[v1[j][k].fi]=d[j]+v1[j][k].se; update= true; } } } if(i==vertex-1 && update)is_negative_cycle=true; else if(!update)break; } return make_tuple(d,is_negative_cycle); } private: ll INF; int vertex; vector<vector<pair<int,ll> > > v1; vector<vector<ll> > v2; }; //tuple tp<int,int,int> -> int a=get<0>(tp),b=get<1>(tp),c=get<2>(tp) int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.precision(10); cout<<fixed; #ifdef LOCAL_DEFINE FILE *stream1; //FILE *stream2; stream1=freopen("in","r",stdin); //stream2=freopen("out","w",stdout); if(stream1==NULL)return 0; //if(stream2==NULL)return 0; #endif cin>>n>>m>>s>>t; s--;t--; shortest_path sp(n); for(int i=0;i<m;i++){ int a,b;cin>>a>>b; a--;b--; sp.add_edge(a,b,1); sp.add_edge(b,a,1); } vector<ll> d=sp.dijkstra(s); vector<ll> d2=sp.dijkstra(t); int st=d[t]; if(st==1){ cout<<0<<endl; }else{ int tmp=st-2; sort(d2.begin(),d2.end()); sort(d.begin(),d.end()); ll ans=0; for(int i=0;i<=tmp;i++){ ll a=upper_bound(d2.begin(),d2.end(),tmp-i)-lower_bound(d2.begin(),d2.end(),tmp-i); ll b=upper_bound(d.begin(),d.end(),i)-lower_bound(d.begin(),d.end(),i); ans+=a*b; //cout<<ans<<endl; } cout<<ans<<endl; } #ifdef LOCAL_DEFINE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n"; fclose(stream1); //fclose(stream2); #endif return 0; }
sからある頂点pまでの最短距離をx、ある頂点qからtまでの最短距離をyとする。
また、sからtまでの最短距離をs_tとすると、求めるものはx+y=s_t-2のものの個数。
これはsが始点のdijkstra、tが始点のdijkstraをやっておいて、各頂点までの距離が昇順になるようソートした後、xの値で全探索する。
そうするとy=s_t-2-xとなるyの個数を二分探索で求められる。
また、sからxが最短距離となるような頂点の数も二分探索で求められるので、それぞれの個数を掛けたものの和が答えになります。
(わかりにくいですね)(説明が下手)