Module: Pengaturcaraan Graf Dinamik


Problem

5 /7


Pintasan ke DAG

Theory Click to read/hide

Dalam penyelesaian menggunakan pengaturcaraan dinamik, urutan pengiraan dinamik adalah penting (perlu nilai yang bergantung pada semasa dikira sebelum ini).
Oleh itu, jika perlu menggunakan pengaturcaraan dinamik pada graf akiklik terarah, pada mulanya perlu membina pengisihan topologi graf. Kemudian hitung dinamik dengan mengisih melalui bucu dalam susunan jenis topologi yang dibina (bergantung pada masalah, susunan traversal boleh sama ada dari sumber ke sink atau sebaliknya).
 
 

Problem

Graf asiklik berwajaran terarah diberikan. Ia diperlukan untuk mencari laluan terpendek di dalamnya
dari bucu s ke bucu t.

Input:
Baris pertama fail input mengandungi empat integer n, m, s dan t - bilangan bucu, tepi graf, bucu awal dan akhir, masing-masing (1 <= n <= 100000; 0 <= m <= 200000; 1 < ;= s, t <= n).
M baris seterusnya mengandungi perihalan tepi, satu setiap baris. 
Nombor tepi i diterangkan oleh tiga integer bi, ei dan wi - masing-masing permulaan, akhir dan panjang tepi ( 1 <= b i, ei <= n;|wi| <= 1000). 
Graf tidak mengandungi kitaran dan gelung.

Output:
Baris pertama fail output mesti mengandungi satu integer - panjang laluan terpendek dari s hingga t. 
Jika tiada laluan dari s ke t, cetak "Tidak boleh dicapai".

Contoh:
 

time 1500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

Input Output
2 1 1 2
1 2 -10 		-10
2 1 2 1
1 2 -10 		Tidak boleh dihubungi