Submission #1406749
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;
struct edge{
int to;
int cost;
};
int n,m,R,T;
ll d[MAX_N][MAX_N];
double usagi[MAX_N][MAX_N];
double kame[MAX_N][MAX_N];
vector<edge> G[MAX_N];
void dijkstra(int s)
{
priority_queue<P,vector<P>,greater<P> > que;
d[s][s] = 0;
que.push(P(0,s));
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(d[s][v] < p.first) continue;
vector<edge>::iterator it = G[v].begin();
rep(i,G[v].size()){
if(d[s][G[v][i].to] > d[s][v] + G[v][i].cost){
d[s][G[v][i].to] = d[s][v] + G[v][i].cost;
que.push(P(d[s][G[v][i].to],G[v][i].to));
}
}
}
}
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;
G[a-1].pb((edge){b-1,c});
G[b-1].pb((edge){a-1,c});
}
rep(i,n){
dijkstra(i);
}
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 |
100 |
Code Size |
2395 Byte |
Status |
AC |
Exec Time |
1445 ms |
Memory |
147072 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 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 |
9 ms |
15232 KB |
subtask1_06.txt |
AC |
12 ms |
15232 KB |
subtask1_07.txt |
AC |
36 ms |
21504 KB |
subtask1_08.txt |
AC |
45 ms |
27648 KB |
subtask1_09.txt |
AC |
370 ms |
83712 KB |
subtask1_10.txt |
AC |
382 ms |
89984 KB |
subtask1_11.txt |
AC |
156 ms |
52608 KB |
subtask1_12.txt |
AC |
1392 ms |
146944 KB |
subtask1_13.txt |
AC |
1387 ms |
146944 KB |
subtask1_14.txt |
AC |
1397 ms |
147072 KB |
subtask1_15.txt |
AC |
855 ms |
123264 KB |
subtask1_16.txt |
AC |
1445 ms |
147072 KB |