Nộp bài Các bài nộp Làm tốt nhất PDF 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

Submit solution!
Đượ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
Xem lại 1  2  3  4  5  6 Xem tiếp >
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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.