C - 正直者の高橋くん / AtCoderBeginnerContest#021
#include <algorithm> #include <functional> #include <iostream> #include <queue> #include <vector> #include <utility> using namespace std; #define INF (1<<29) const long long MOD = 1e9+7; struct edge { int to, cost; edge(int a, int b) {to=a, cost=b;} }; typedef pair<int,int> P_II; vector<edge> G[100]; int Dijkstra(int n, int s, int g) { long long d[100], answer[100]={0}; bool flg[100]={false}; priority_queue< P_II,vector<P_II>,greater<P_II> > que; fill (d,d+n,INF); d[s]=0; answer[s]=1; que.push( P_II(0,s) ); while ( !que.empty() ) { P_II p=que.top(); que.pop(); int v=p.second; if (d[v] < p.first) continue; if (flg[v]) continue; flg[v]=true; for (int i=0; i<G[v].size(); ++i) { edge e=G[v][i]; if (d[e.to] >= d[v]+e.cost) { answer[e.to]=(answer[e.to]+answer[v])%MOD; d[e.to]=d[v]+e.cost; que.push( P_II(d[e.to],e.to) ); } } } return answer[g]; } void Solve(int n) { int a, b, m, x, y; cin >> a >> b; cin >> m; for (int i=0; i<m; ++i) { cin >> x >> y; G[x-1].push_back( edge(y-1,1) ); G[y-1].push_back( edge(x-1,1) ); } cout << Dijkstra(n,a-1,b-1) << endl; } int main(void) { int n; cin >> n; Solve(n); return 0; }
ダイクストラ法で最短経路を求めつつ重複しないようにフラグを立て、目的地までの通り数を出力。
〜了〜