Submission #1942502
Source Code Expand
#include <bits/stdc++.h>
#define int long long
#define double long double
#define N 100010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T> void prArr(T a,string s = " "){
for(int i=0;i<(int)a.size();i++)cout<<(i? s:"")<<a[i];cout<<endl;
}
vector<vector<P> > G;
vector<int> dijkstra(int start){
vector<int> D(G.size(),INF);
priority_queue<P,vector<P>,greater<P> > Q;
Q.push(P(0,start));
D[start] = 0;
while(!Q.empty()){
P t = Q.top();Q.pop();
int cost = t.first;
int pos = t.second;
if(D[pos] < cost) continue;
for(auto p:G[pos]){
int to = p.first;
int ncost = cost + p.second;
if(D[to] <= ncost) continue;
D[to] = ncost;
Q.push(P(ncost,to));
}
}
return D;
}
signed main(){
int n,m,R,T;
cin>>n>>m>>R>>T;
G.resize(n);
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c; a--,b--;
G[a].push_back(P(b,c));
G[b].push_back(P(a,c));
}
int ans = 0;
for(int C=0;C<n;C++){
vector<int> D = dijkstra(C);
sort(D.begin(),D.end());
for(int A=1;A<n;A++){
int B = lower_bound(D.begin(),D.end(), 1.0*D[A]*T/R) - D.begin()-1;
if(A<=B) B--;
if(B >= 0) ans += B;
}
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
haji |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1682 Byte |
Status |
AC |
Exec Time |
1113 ms |
Memory |
512 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 |
1 ms |
256 KB |
subtask0_sample-02.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
6 ms |
256 KB |
subtask1_06.txt |
AC |
9 ms |
256 KB |
subtask1_07.txt |
AC |
29 ms |
384 KB |
subtask1_08.txt |
AC |
38 ms |
384 KB |
subtask1_09.txt |
AC |
317 ms |
384 KB |
subtask1_10.txt |
AC |
304 ms |
384 KB |
subtask1_11.txt |
AC |
132 ms |
384 KB |
subtask1_12.txt |
AC |
1030 ms |
512 KB |
subtask1_13.txt |
AC |
1021 ms |
512 KB |
subtask1_14.txt |
AC |
1101 ms |
512 KB |
subtask1_15.txt |
AC |
728 ms |
512 KB |
subtask1_16.txt |
AC |
1113 ms |
512 KB |