Tổng đường đi

View as PDF

Submit solution

Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Cho đồ thị có hướng không chu trình và 2 đỉnh s,t. Cho biết có bao nhiêu đường đi từ s đến t (hai đường đi khác nhau nếu như thứ tự các đỉnh trên chúng khác nhau)

Dữ liệu vào

  • Dòng đầu tiên gồm 4 số nguyên dương n,m,s,t (n,m105,s,tn) lần lượt là số đỉnh, số cạnh và 2 đỉnh s,t như miêu tả của đề bài
  • m dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương u,v thể hiện một cạnh đi từ u tới v

Dữ liệu ra

  • Một số nguyên duy nhất là số đường đi từ s tới t, vì kết quả có thể rất lớn nên hãy in kết quả chia lấy dư cho 109+7
Ví dụ:
Input
Copy
10 14 5 7
3 2
9 7
5 4
4 10
1 5
1 2
7 6
10 6
8 3
5 8
5 10
5 3
5 9
5 2
Output
Copy
1

Comments

Please read the guidelines before commenting.



  • 1
    loc  commented 7:18:36 am, 27/10/2021 edited

    đáp án được mod 1e9+7 nhé và limit n,m <=1e5 nhé


    • 0
      Nhatthang27  commented 7:28:38 am, 27/10/2021

      cảm ơn Lộc


    • 0
      PhiLong  commented 7:23:21 am, 27/10/2021

      cho minh xin limit n,m với được hem (^-^)


      • -3
        loc  commented 7:28:27 am, 27/10/2021

        dễ thương quá


        • 0
          AnhLaGio  commented 3:19:12 am, 30/10/2021

          '.'