Untitled
plain_text
a month ago
1.9 kB
0
Indexable
Never
#include <iostream> using namespace std; #define MAX 9999999 using namespace std; int n; int mem; bool visited[201]; int parent[201]; int key[201]; int arr[201][201]; int x[201], y[201], k[201]; void Dijkstra(int u){ key[u] = 0; for(int i=0; i<n; i++){ /*for(int p=0; p<n; p++){ if(visited[p] == false){ mem = p; break; } }*/ //int min = key[mem]; int min = MAX; mem = -1; for(int j=0; j<n; j++){ if(visited[j] == false){ if(key[j] < min){ min = key[j]; mem = j; } } } if(mem == -1) return; visited[mem] = true; for(int k=0; k<n; k++){ if(visited[k] == false && arr[mem][k] != 0){ if(key[k] > key[mem] + arr[mem][k]){ key[k] = key[mem] + arr[mem][k]; } } } } } int main(){ //freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n; for(int i=0; i<n; i++){ key[i] = MAX; parent[i] = -1; visited[i] = false; } for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ arr[i][j] = 0; } } for(int i=0; i<n; i++){ cin >> x[i] >> y[i] >> k[i]; } for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ long long td = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]); long long kc1 = (40 + k[i] + k[j]); long long kc2 = (90 + k[i] + k[j]); if(i==j){ arr[i][j] = 0; } else if(td <= kc1 * kc1){ arr[i][j] = 1; } else if(td <= kc2 * kc2){ arr[i][j] = 400; } else{ arr[i][j] = 0; } } } /*cout << endl; for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ cout << arr[i][j] << " "; } cout << endl; }*/ Dijkstra(0); if(key[n-1] == MAX){ cout << "-1" << endl; } else cout << key[n-1]/400 << " " << key[n-1]%400 << endl; } return 0; }