Submission #383585


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long int64;
typedef pair< int, int > Pi;
typedef vector< vector< int > > Graph;

vector< int > min_cost;

int Dijkstra(Graph& info, int s, int g) { //sからgへの最短路
  typedef pair< int, int > Pi;
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  min_cost.resize(info.size(), -1);
  que.push( Pi( 0, s));
  min_cost[s] = 0;
  while(!que.empty()){
    Pi p = que.top(); que.pop();
    for(int i = 0; i < info[p.second].size(); i++){
      int e = info[p.second][i];
      if(min_cost[e] == -1 || p.first + 1 < min_cost[e]){
        min_cost[e] = p.first + 1;
        que.push( Pi( min_cost[e], e));
      }
    }
  }
  return -1;
}
int dp[100];

int rec(Graph& g, int a, int b) {
  if(~dp[a]) return(dp[a]);
  if(a == b) return(1);
  int ret = 0;
  for(int i = 0; i < g[a].size(); i++) {
    if(min_cost[g[a][i]] + 1 == min_cost[a]) {
      (ret += rec(g, g[a][i], b)) %= 1000000007;
    }
  }
  return(dp[a] = ret);
}


int main() {
  fill_n(dp, 100, -1);
  int N, a, b, M;
  cin >> N;
  cin >> a >> b;
  --a, --b;
  cin >> M;
  Graph g(N);
  for(int i = 0; i < M; i++){
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  Dijkstra(g, b, a);
  cout << rec(g, a, b) << endl;
}

Submission Info

Submission Time
Task C - 正直者の高橋くん
User ei13333
Language C++ (GCC 4.9.2)
Score 100
Code Size 1402 Byte
Status
Exec Time 30 ms
Memory 932 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt
All 100 / 100 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt, subtask1_30.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt 25 ms 928 KB
subtask0_sample_02.txt 23 ms 928 KB
subtask1_01.txt 25 ms 920 KB
subtask1_02.txt 25 ms 920 KB
subtask1_03.txt 27 ms 924 KB
subtask1_04.txt 27 ms 784 KB
subtask1_05.txt 23 ms 928 KB
subtask1_06.txt 24 ms 932 KB
subtask1_07.txt 23 ms 804 KB
subtask1_08.txt 24 ms 800 KB
subtask1_09.txt 24 ms 716 KB
subtask1_10.txt 25 ms 924 KB
subtask1_11.txt 22 ms 920 KB
subtask1_12.txt 22 ms 800 KB
subtask1_13.txt 23 ms 804 KB
subtask1_14.txt 23 ms 876 KB
subtask1_15.txt 24 ms 924 KB
subtask1_16.txt 22 ms 928 KB
subtask1_17.txt 23 ms 932 KB
subtask1_18.txt 24 ms 924 KB
subtask1_19.txt 25 ms 928 KB
subtask1_20.txt 24 ms 920 KB
subtask1_21.txt 24 ms 928 KB
subtask1_22.txt 24 ms 804 KB
subtask1_23.txt 24 ms 800 KB
subtask1_24.txt 22 ms 796 KB
subtask1_25.txt 25 ms 844 KB
subtask1_26.txt 25 ms 792 KB
subtask1_27.txt 25 ms 924 KB
subtask1_28.txt 30 ms 788 KB
subtask1_29.txt 23 ms 920 KB
subtask1_30.txt 25 ms 796 KB