Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- //speed coding handle
- #define mp make_pair
- #define cve(tpy) for (auto i : tpy) {for(auto j : i){cout << j << " "; }cout << "\n";} ;
- #define f first
- #define s second
- #define loop(i, x, n) for (int i = x; i < n; i++)
- #define joop(x, n) for (ll j = x; j < n; j++)
- #define lp(n) for (ll i = 0; i < n; i++)
- #define err cout << "ERROR" << endl;
- #define all(x) x.begin(), x.end()
- #define pb push_back
- #define sz(x) x.size()
- #define rndm rng()
- // types
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define vvi vector<vector<int>>
- #define vvll vector<vector<ll>>
- typedef long long ll;
- typedef long double ld;
- // types of data
- #define inf 1000000000
- #define infll 1000000000000000000
- #define INF ll(1e9)
- #define md 998244353
- #define mod 1000000009
- //#define K 239017
- #define DEBUG 1
- using namespace std;
- mt19937_64 rng(113113);
- uniform_int_distribution<ll> drist;
- //const int INF = std::numeric_limits<int>::max();
- const int MAX_N = 50;
- int N, m; // количество локаций
- float graph[MAX_N][MAX_N]; // матрица смежности
- float speed[3]; // скорости роботов
- void dijkstra(int start, float dist[], float r_speed, int prev[]) {
- bool visited[MAX_N] = {false};
- // loop(i, 0, MAX_N){
- // cout << visited[i] << " ";
- // }
- cout << "\n";
- prev[start] = start;
- for (int i = 0; i < N; ++i) {
- dist[i] = INF;
- }
- dist[start] = 0;
- for (int i = 0; i < N; ++i) {
- int u = -1;
- for (int j = 0; j < N; ++j) {
- if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
- u = j;
- }
- }
- // cout << "u: " << u << endl;
- if (dist[u] == INF) break;
- visited[u] = true;
- for (int v = 0; v < N; ++v) {
- // if(v == 2){
- // cout << "u: " << u << " g: " << graph[u][v] << endl;
- // }
- if (graph[u][v] && dist[u] + graph[u][v] / r_speed < dist[v]) {
- dist[v] = dist[u] + graph[u][v]/r_speed;
- // cout << "u: " << u << " v: " << v << endl;
- prev[v] = u;
- }
- }
- }
- }
- int I[3];
- void input(){
- cin >> N >> m;
- for(int i = 0; i < N; ++i) {
- for(int j = 0; j < N; ++j) {
- cin >> graph[i][j];
- }
- }
- loop(i, 0, m){
- cin >> I[i];
- }
- loop(i, 0, m){
- cin >> speed[i];
- }
- }
- void solve(){
- input();
- float mind = -1;
- int prev[3][MAX_N];
- float d[3][MAX_N];
- loop(i, 0, 3){
- loop(j, 0, MAX_N){
- prev[i][j] = 0;
- d[i][j] = inf;
- cout << d[i][j] << " ";
- }
- cout << "\n";
- }
- loop(i, 0, N){
- loop(j, 0, N){
- cout << graph[i][j] << " ";
- }
- cout << "\n";
- }
- // cout << "m: " << m << endl;
- loop(i, 0, m){
- dijkstra(I[i], d[i], speed[i], prev[i]);
- }
- cout << "prev: \n";
- loop(i, 0, m){
- loop(j, 0, N){
- cout << prev[i][j] << " ";
- }
- cout << "\n";
- }
- cout << "\ndist: \n";
- loop(i, 0, m){
- loop(j, 0, N){
- cout << d[i][j] << " ";
- }
- cout << "\n";
- }
- loop(p, 0, N) {
- float t[3];
- float middleware = 1;
- loop(i, 0, m){
- float dis = d[i][p];
- t[i] = dis;
- middleware = max(middleware, dis);
- }
- // if(t[0] == t[1] or t[0] == t[2] or t[1] == t[2]){
- // mind = min(mind, middleware);
- // err
- // cout << t[0] << " " << t[1] << " " << t[2] << endl;
- // // ------------------------------------ ? -------------------------
- // }
- float w = inf;
- loop(i, 0, m){
- loop(j, 0, m){
- if(i != j){ // перебираю всех разных роботов
- // cout << p << " " << prev[i][p] << " i: " << i << endl;
- // проверка если столкнутся на дороге
- // if(graph[p][prev[i][p]] == 0 or graph[prev[i][p]][p] == 0 or graph[prev[j][p]][p] == 0){
- // cout << "Never met\n";
- // cout << graph[p][prev[i][p]] << " " << prev[i][p] ;
- // return;
- // }
- if(d[i][I[j]] == inf){
- cout << "Never met";
- return;
- }
- if(d[i][prev[i][p]] == d[j][p] and graph[p][prev[i][p]] != 0){
- // если стояли рядом и их путь одинаковый
- // err
- w = min(w, d[j][p] + graph[p][prev[i][p]]/(speed[j] + speed[i]));
- if(mind == 0){
- cout << "mind = 0\n";
- cout << d[j][p] << " " << graph[p][prev[i][p]] << '\n';
- }
- }
- // проверка если столкнутся на пункте
- if(d[i][prev[i][p]] == d[j][prev[j][p]] and graph[prev[i][p]][p] != 0 and graph[prev[j][p]][p] != 0){
- cout << "dist len: " << d[i][p] + d[j][p] << endl;
- w = min(w, d[i][prev[i][p]] + (graph[prev[i][p]][p] + graph[prev[j][p]][p]) / (speed[j] + speed[i]) );
- }
- }
- if(w != inf){
- mind = max(mind, w);
- }
- }
- }
- }
- if(mind == inf){
- cout << "Never meet\n";
- return;
- }
- cout << "Min time for robots:" << mind << endl;
- }
- int main() {
- freopen("text.txt", "r", stdin);
- solve();
- return 1;
- }
Advertisement
Advertisement