Submission #1942476


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);
    D.erase(D.begin()+C);
    sort(D.begin(),D.end());
    
    for(int A=0;A<n-1;A++){
      int B = lower_bound(D.begin(),D.end(), 1.0*D[A]*T/R) - D.begin()-1;
      if(B == -1) continue;
      ans += B+1;
    }
  }
  
  cout<<ans<<endl;
  return 0;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User haji
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1711 Byte
Status WA
Exec Time 1130 ms
Memory 512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 15
WA × 3
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 317 ms 384 KB
subtask1_10.txt AC 305 ms 384 KB
subtask1_11.txt AC 132 ms 384 KB
subtask1_12.txt WA 1031 ms 512 KB
subtask1_13.txt AC 1033 ms 512 KB
subtask1_14.txt AC 1122 ms 512 KB
subtask1_15.txt AC 738 ms 512 KB
subtask1_16.txt AC 1130 ms 512 KB