Submission #1406741
Source Code Expand
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl
using namespace std;
typedef pair<int,int>P;
const int MAX_N = 2501;
int n,m,R,T;
ll d[MAX_N][MAX_N];
double usagi[MAX_N][MAX_N];
double kame[MAX_N][MAX_N];
void warshall_floyd()
{
rep(i,n){
rep(j,n){
rep(k,n){
d[j][k] = min(d[j][k],d[j][i]+d[i][k]);
}
}
}
}
int main()
{
cin >> n >> m >> R >> T;
rep(i,n){
rep(j,n){
d[i][j] = INF;
}
}
rep(i,m){
int a,b,c;
cin >> a >> b >> c;
d[a-1][b-1] = c;
d[b-1][a-1] = c;
}
warshall_floyd();
rep(i,n){
rep(j,n){
if(i == j){
usagi[j][i] = INF;
kame[j][i] = INF;
}else{
usagi[j][i] = (double)d[i][j] / R;
kame[j][i] = (double)d[i][j] / T;
}
}
}
ll ans = 0;
rep(i,n){
vector<int> vec(n,0);
rep(j,n){
if(j != i){
if(kame[i][j] <= usagi[i][j]-EPS){
vec[j]++;
}
}
}
sort(kame[i],kame[i]+n);
rep(j,n){
if(j != i){
double cri = usagi[i][j];
int cnt = lower_bound(kame[i],kame[i]+n,cri-EPS) - kame[i];
ans += (cnt-vec[j]);
}
}
}
cout << ans << "\n";
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
kopricky |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2008 Byte |
Status |
TLE |
Exec Time |
7356 ms |
Memory |
89856 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample-01.txt, subtask0_sample-02.txt |
All |
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample-01.txt |
AC |
2 ms |
4352 KB |
subtask0_sample-02.txt |
AC |
2 ms |
4352 KB |
subtask1_01.txt |
AC |
2 ms |
6528 KB |
subtask1_02.txt |
AC |
3 ms |
8576 KB |
subtask1_03.txt |
AC |
3 ms |
8576 KB |
subtask1_04.txt |
AC |
2 ms |
4352 KB |
subtask1_05.txt |
AC |
16 ms |
15104 KB |
subtask1_06.txt |
AC |
17 ms |
15104 KB |
subtask1_07.txt |
AC |
43 ms |
21376 KB |
subtask1_08.txt |
AC |
88 ms |
27648 KB |
subtask1_09.txt |
AC |
2572 ms |
83712 KB |
subtask1_10.txt |
AC |
3353 ms |
89856 KB |
subtask1_11.txt |
AC |
606 ms |
52480 KB |
subtask1_12.txt |
TLE |
7355 ms |
50560 KB |
subtask1_13.txt |
TLE |
7356 ms |
50560 KB |
subtask1_14.txt |
TLE |
7356 ms |
50560 KB |
subtask1_15.txt |
TLE |
7355 ms |
41216 KB |
subtask1_16.txt |
TLE |
7355 ms |
50560 KB |