Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
ROADS - Roads |
English | Vietnamese |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/roads
Có N thành phố 1..N nối bởi các con đường một chiều. Mỗi con đường có hai giá trị: độ dài và chi phí phải trả để đi qua. Bob ở thành phố 1. Bạn hãy giúp Bob tìm đường đi ngắn nhất đến thành phố N, biết rằng Bob chỉ có số tiền có hạn là K mà thôi.
Dữ liệu
Dòng đầu tiên ghi t là số test. Với mỗi test, dòng đầu ghi K (0 ≤ K ≤ 10000). Dòng 2 ghi N, 2 ≤ N ≤ 100. Dòng 3 ghi R, 1 ≤ R ≤ 10000 là số đường nối. Mỗi dòng trong N dòng sau ghi 4 số nguyên S, D, L, T mô tả một con đường nối giữa S và D với độ dài L ( 1 ≤ L ≤ 100) và chi phí T (0 ≤ T ≤ 100). Lưu ý có thể có nhiều con đường nối giữa hai thành phố.
Kết quả
Với mỗi test, in ra độ dài đường đi ngắn nhất từ 1 đến N mà tổng chi phí không quá K. Nếu không tồn tại, in ra -1.
Ví dụ
Dữ liệu 2 5 6 7 1 2 2 3 2 4 3 3 3 4 2 4 1 3 4 1 4 6 2 1 3 5 2 0 5 4 3 2 0 4 4 1 4 5 2 1 2 1 0 2 3 1 1 3 4 1 0 Kết quả 11 -1
Được gửi lên bởi: | Jimmy |
Ngày: | 2005-04-28 |
Thời gian chạy: | 7s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
Nguồn bài: | Central European Olympiad in Informatics 98 |
hide comments
|
|||||||||
2020-08-01 06:24:55
bài ga' vl |
|||||||||
2020-02-21 04:40:59 nguyen ngoc son
package bai3; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class main { private static Scanner scanner; private static int[][] arrs; private static int[][] visited; static int dx[] = {-1,-2,-2,-1,1,2,2,1}; static int dy[] = {-2,-1,1,2,2,1,-1,-2}; private static int kQ; /*ham doc vao ma tran*/ public static void readMX() { for (int i = 0; i < arrs.length; i++) { for (int j = 0; j < arrs.length; j++) { arrs[i][j] = scanner.nextInt(); } } } /*ham in ra ma tran*/ public static void printMX() { for (int i = 0; i < arrs.length; i++) { for (int j = 0; j < arrs.length; j++){ System.out.print(arrs[i][j]+" "); } System.out.println(); } } /*ham dem tai vi tri x,y*/ public static int Count(int x,int y) { int cnt = 0; for(int k=0;k<8;k++) { int tx = x + dx[k]; int ty = y + dy[k]; if(tx>=0 &&tx<arrs.length && ty>=0 &&ty<arrs.length && arrs[tx][ty]==1 && visited[tx][ty] == 0) { visited[tx][ty] = 1; cnt++; } } return cnt; } public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("C:\\Users\\SVMC\\eclipse-workspace\\bai3\\src\\bai3\\input.txt")); scanner = new Scanner(System.in); int test_cases = scanner.nextInt(); // System.out.println(test_cases); for (int test = 1; test <= test_cases; test++) { kQ = 0; int N = scanner.nextInt(); int M = scanner.nextInt(); arrs = new int[N][M]; visited = new int[N][M]; readMX(); for (int i = 0; i < arrs.length; i++) { for (int j = 0; j < arrs.length; j++) { if(arrs[i][j]==2) { kQ += Count(i, j); } } } System.out.println("#"+test+" "+kQ); } } } |
|||||||||
2020-02-21 02:44:43 nguyen ngoc son
8 8 1 1 0 1 1 0 2 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1 0 2 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 1 1 0 0 2 0 1 1 0 1 1 1 0 0 1 0 1 0 1 8 8 0 0 1 1 1 0 1 1 0 2 0 1 1 0 0 0 0 0 1 1 1 2 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 0 1 2 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 0 1 2 1 1 8 8 1 1 0 0 0 0 1 0 1 1 0 2 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 2 0 0 0 0 1 0 1 1 1 1 0 2 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 2 1 1 1 0 15 15 0 0 0 1 1 1 0 0 1 0 0 0 1 2 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 1 1 1 2 0 0 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 2 0 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 2 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 2 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 0 1 1 0 0 1 1 2 1 1 1 0 15 15 1 0 1 0 0 1 1 2 1 1 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 1 0 0 2 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 1 2 1 0 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 2 0 0 1 1 0 1 0 0 #1 6 #2 14 #3 9 #4 17 #5 8 |
|||||||||
2019-08-10 14:44:26
cai de no sai sai hay sao ay :v |
|||||||||
2019-07-29 08:56:32
1 đấm ac code: https://bit.ly/2eGhgab . Khỏi cảm ơn |
|||||||||
2019-03-25 10:37:12
làm bằng quay lui thì chạy quá thời gian T_T |
|||||||||
2019-02-20 14:50:23
ai ngờ khó thật |
|||||||||
2019-02-20 14:49:51
lúc đầu đọc cmt thấy đệ quy tưởng khó lắm :))) |
|||||||||
2018-09-04 16:56:24
nhật hào sạch |
|||||||||
2018-06-06 11:22:56
dijsktra |