Submission #1942483
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;
ans += B;
}
}
cout<<ans<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
haji |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1648 Byte |
Status |
WA |
Exec Time |
1115 ms |
Memory |
512 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 |
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 |
WA |
9 ms |
256 KB |
subtask1_07.txt |
AC |
29 ms |
384 KB |
subtask1_08.txt |
WA |
37 ms |
384 KB |
subtask1_09.txt |
AC |
319 ms |
384 KB |
subtask1_10.txt |
AC |
302 ms |
384 KB |
subtask1_11.txt |
AC |
131 ms |
384 KB |
subtask1_12.txt |
WA |
1028 ms |
512 KB |
subtask1_13.txt |
AC |
1022 ms |
512 KB |
subtask1_14.txt |
AC |
1107 ms |
512 KB |
subtask1_15.txt |
AC |
727 ms |
512 KB |
subtask1_16.txt |
AC |
1115 ms |
512 KB |