Submission #1046413
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
int len = v.size(); s << "\n";
for (int i = 0; i < len; ++i) {
s << v[i]; if (i < len - 1) s << "\t";
}
s << "\n"; return s;
}
// cout deque
template<typename T> ostream& operator<<(ostream& s, const deque<T>& v) {
int len = v.size(); s << "\n";
for (int i = 0; i < len; ++i) {
s << v[i]; if (i < len - 1) s << "\t";
}
s << "\n"; return s;
}
// cout 2-dimentional vector
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
int len = vv.size();
for (int i = 0; i < len; ++i) { s << vv[i]; }
return s;
}
// cout 2-dimentional deque
template<typename T> ostream& operator<<(ostream& s, const deque< deque<T> >& vv) {
int len = vv.size();
for (int i = 0; i < len; ++i) { s << vv[i]; }
return s;
}
#define INF DBL_MAX/4
int n;
vv<double> cost;
vector<double> d; // 仮のコストの最小値、最終結果
deque<bool> used;
void dijkstra(int s) {
d.assign(n, INF);
used.assign(n, false);
d[s] = 0;
while (true) {
int v = -1;
rep (u, n) {
if (!used[u] && (v == -1 || d[u] < d[v])) {
v = u;
}
}
if (v == -1) {
break;
}
used[v] = true;
rep (u, n) {
d[u] = min(d[u], d[v] + cost[v][u]);
}
}
}
int main() {
scanf("%d", &n);
vector<double> x(n), y(n), t(n), r(n);
rep (i, n) {
scanf("%lf %lf %lf %lf", &x[i], &y[i], &t[i], &r[i]);
}
if (n == 1) {
printf("0\n");
return 0;
}
cost.assign(n, vector<double>(n, INF));
rep (i, n) {
double dx;
double dy;
double dist;
double vij;
double vji;
rep (j, n) {
if (i == j) {
continue;
}
dx = x[i] - x[j];
dy = y[i] - y[j];
dist = sqrt(dx*dx + dy*dy);
vij = min(t[i], r[j]);
vji = min(t[j], r[i]);
cost[i][j] = dist / vij;
cost[j][i] = dist / vji;
}
}
dijkstra(0);
sort(all(d), greater<double>());
rep (i, n-1) {
d[i] += i;
}
sort(all(d), greater<double>());
printf("%.9f\n", d[0]);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - THE☆たこ焼き祭り2012 |
User |
tspcx |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
3106 Byte |
Status |
AC |
Exec Time |
52 ms |
Memory |
8740 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:100:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
./Main.cpp:103:57: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lf %lf %lf %lf", &x[i], &y[i], &t[i], &r[i]);
^
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 00_sample_05.txt, 01_rand_00.txt, 01_rand_01.txt, 01_rand_02.txt, 01_rand_03.txt, 01_rand_04.txt, 01_rand_05.txt, 01_rand_06.txt, 01_rand_07.txt, 01_rand_08.txt, 01_rand_09.txt, 02_maxrand_00.txt, 02_maxrand_01.txt, 02_maxrand_02.txt, 02_maxrand_03.txt, 02_maxrand_04.txt, 02_maxrand_05.txt, 02_maxrand_06.txt, 02_maxrand_07.txt, 02_maxrand_08.txt, 02_maxrand_09.txt, 03_slow_00.txt, 03_slow_01.txt, 03_slow_02.txt, 03_slow_03.txt, 03_slow_04.txt, 03_slow_05.txt, 03_slow_06.txt, 03_slow_07.txt, 03_slow_08.txt, 03_slow_09.txt, 04_logspeed_00.txt, 04_logspeed_01.txt, 04_logspeed_02.txt, 04_logspeed_03.txt, 04_logspeed_04.txt, 04_logspeed_05.txt, 04_logspeed_06.txt, 04_logspeed_07.txt, 04_logspeed_08.txt, 04_logspeed_09.txt |
Case Name |
Status |
Exec Time |
Memory |
00_min.txt |
AC |
18 ms |
800 KB |
00_sample_01.txt |
AC |
19 ms |
800 KB |
00_sample_02.txt |
AC |
18 ms |
800 KB |
00_sample_03.txt |
AC |
19 ms |
804 KB |
00_sample_04.txt |
AC |
17 ms |
804 KB |
00_sample_05.txt |
AC |
19 ms |
800 KB |
01_rand_00.txt |
AC |
20 ms |
1052 KB |
01_rand_01.txt |
AC |
24 ms |
2208 KB |
01_rand_02.txt |
AC |
35 ms |
4772 KB |
01_rand_03.txt |
AC |
21 ms |
1316 KB |
01_rand_04.txt |
AC |
22 ms |
1564 KB |
01_rand_05.txt |
AC |
20 ms |
1176 KB |
01_rand_06.txt |
AC |
23 ms |
1948 KB |
01_rand_07.txt |
AC |
26 ms |
2640 KB |
01_rand_08.txt |
AC |
18 ms |
916 KB |
01_rand_09.txt |
AC |
33 ms |
4516 KB |
02_maxrand_00.txt |
AC |
49 ms |
8732 KB |
02_maxrand_01.txt |
AC |
49 ms |
8608 KB |
02_maxrand_02.txt |
AC |
49 ms |
8692 KB |
02_maxrand_03.txt |
AC |
49 ms |
8696 KB |
02_maxrand_04.txt |
AC |
47 ms |
8608 KB |
02_maxrand_05.txt |
AC |
48 ms |
8604 KB |
02_maxrand_06.txt |
AC |
51 ms |
8688 KB |
02_maxrand_07.txt |
AC |
49 ms |
8568 KB |
02_maxrand_08.txt |
AC |
50 ms |
8612 KB |
02_maxrand_09.txt |
AC |
50 ms |
8732 KB |
03_slow_00.txt |
AC |
50 ms |
8572 KB |
03_slow_01.txt |
AC |
48 ms |
8696 KB |
03_slow_02.txt |
AC |
47 ms |
8568 KB |
03_slow_03.txt |
AC |
51 ms |
8688 KB |
03_slow_04.txt |
AC |
46 ms |
8564 KB |
03_slow_05.txt |
AC |
48 ms |
8608 KB |
03_slow_06.txt |
AC |
49 ms |
8696 KB |
03_slow_07.txt |
AC |
49 ms |
8652 KB |
03_slow_08.txt |
AC |
47 ms |
8604 KB |
03_slow_09.txt |
AC |
52 ms |
8688 KB |
04_logspeed_00.txt |
AC |
48 ms |
8680 KB |
04_logspeed_01.txt |
AC |
49 ms |
8740 KB |
04_logspeed_02.txt |
AC |
49 ms |
8608 KB |
04_logspeed_03.txt |
AC |
50 ms |
8612 KB |
04_logspeed_04.txt |
AC |
47 ms |
8604 KB |
04_logspeed_05.txt |
AC |
49 ms |
8740 KB |
04_logspeed_06.txt |
AC |
48 ms |
8728 KB |
04_logspeed_07.txt |
AC |
49 ms |
8696 KB |
04_logspeed_08.txt |
AC |
51 ms |
8592 KB |
04_logspeed_09.txt |
AC |
49 ms |
8612 KB |