the_frog
duyvan
plain_text
a year ago
1.9 kB
9
Indexable
#include <iostream> using namespace std; int T, N; int Oxy[200][3]; int results, jump_short, jump_long, tt_short; int matrix[200][200]; int visit[200]; struct Node { int r, c; }; int Queue[1000000]; int front, rear; void enQueue(int x){ rear++; Queue[rear] = x; } int deQueue(){ front++; return Queue[front]; } int distan(int index1, int index2){ int a = Oxy[index1][0] - Oxy[index2][0]; int b = Oxy[index1][1] - Oxy[index2][1]; return (a*a + b*b); } int check(int index1, int index2){ int dis = distan(index1,index2); int a = 40 + Oxy[index1][2] + Oxy[index2][2]; int b = 90 + Oxy[index1][2] + Oxy[index2][2]; if (a*a > dis) return 1; else if (b*b > dis) return 10000; return 0; } int main(){ freopen("input.txt","r",stdin); cin >> T; for (int t = 0; t < T; t++){ cin >> N; results = -1; jump_short = jump_long = 100000; for (int i = 0; i < N; i++){ cin >> Oxy[i][0] >> Oxy[i][1] >> Oxy[i][2]; visit[i] = -1; } for (int i = 0; i < N; i++){ for (int j = i + 1; j < N; j++){ matrix[i][j] = check(i,j); matrix[j][i] = matrix[i][j]; } matrix[i][i] = -1; } front = rear = -1; enQueue(0); visit[0] = 0; while (front != rear){ int node = deQueue(); if (node == N - 1) { if (visit[node] < results || results == -1){ results = visit[node]; } } else { for (int i = 1; i < N; i++){ if (matrix[node][i] > 0) { if (visit[i] == -1 || visit[i] > matrix[node][i] + visit[node]){ visit[i] = matrix[node][i] + visit[node]; enQueue(i); } } } } } if (results == -1) cout << results << endl; else { jump_long = results/10000; jump_short = results%10000; cout << jump_long << " " << jump_short << endl; } } return 0; } //con ech nhay duong ngan nhat
Editor is loading...
Leave a Comment