Submission #1481460


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n,m,r,t;
  cin>>n>>m>>r>>t;
  typedef pair<int,int> P;
  vector<vector<P> > G(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 i=0;i<n;i++){
    int d[n];
    fill(d,d+n,1LL<<55LL);
    priority_queue<P,vector<P>,greater<P> > q;
    d[i]=0;
    q.push(P(d[i],i));
    while(!q.empty()){
      P p=q.top();q.pop();
      int v=p.second;
      if(d[v]<p.first) continue;
      //cout<<v<<" "<<d[v]<<endl;
      for(P e:G[v]){
	int u=e.first,c=e.second;
	//cout<<u<<":"<<c<<endl;
	//cout<<d[u]<<endl;
	if(d[u]>d[v]+c){
	  d[u]=d[v]+c;
	  q.push(P(d[u],u));
	}
      }
    }
    for(int j=0;j<n;j++) d[j]*=t;
    sort(d,d+n);
    for(int j=1;j<n;j++){
      auto latte=upper_bound(d,d+n,r*d[j]/t);
      ans+=d+n-latte;
    }
    //cout<<ans<<endl;
    //cout<<"i:"<<i<<endl;
    //for(int j=0;j<n;j++) cout<<d[j]<<endl;
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Submission Time
Task C - ウサギとカメ
User beet
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1100 Byte
Status WA
Exec Time 1133 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 8 ms 256 KB
subtask1_07.txt AC 29 ms 384 KB
subtask1_08.txt WA 37 ms 384 KB
subtask1_09.txt AC 337 ms 384 KB
subtask1_10.txt AC 327 ms 384 KB
subtask1_11.txt AC 138 ms 384 KB
subtask1_12.txt WA 1040 ms 512 KB
subtask1_13.txt AC 1039 ms 512 KB
subtask1_14.txt AC 1133 ms 512 KB
subtask1_15.txt AC 773 ms 512 KB
subtask1_16.txt AC 1133 ms 512 KB