Submission #2935322


Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<double,int> P;
int N,M;
const double inf = 1e9;
double a,b,c,R,T;
vector<vector<P>> v(2510),u(2510);
int main(){
	cin >> N >> M >> R >> T;
	for(int i=0;i<M;i++){
		cin >> a >> b >> c;
		v[a].push_back(P(c,b));
		v[b].push_back(P(c,a));
	}
	int ans = 0;
	vector<double> CR(N+1);
	for(int r=1;r<=N;r++){
		priority_queue<P> Q;
		Q.push(P(0,r));
		for(int i=1;i<=N;i++){
			CR[i] = inf;
		}
		CR[r] = 0;
		while(!Q.empty()){
			P t = Q.top();
			int  s = t.second;
			Q.pop();
			if(CR[s] < t.first) continue;
			for(int i=0;i<v[s].size();i++){
				P e = v[s][i];
				if(CR[e.second] > CR[s] + e.first){
					CR[e.second] = CR[s] + e.first;
					Q.push(make_pair(-CR[e.second],e.second));
				}
			}
		}
		sort(CR.begin()+1,CR.begin()+N+1);
		for(int i=2;i<=N;i++){
			if(R>=T){
				decltype(CR)::iterator it = upper_bound(CR.begin(),CR.end(),CR[i]*R/T);
				ans += (N-(it-CR.begin()-1));
			}
			else{
				decltype(CR)::iterator it = upper_bound(CR.begin(),CR.end(),CR[i]*T/R);
				ans += it-CR.begin()-1;
			}
		}
	}
	cout << ans << endl;
}

Submission Info

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

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 2
AC × 12
WA × 6
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 384 KB
subtask0_sample-02.txt AC 1 ms 384 KB
subtask1_01.txt AC 1 ms 384 KB
subtask1_02.txt AC 1 ms 384 KB
subtask1_03.txt AC 1 ms 384 KB
subtask1_04.txt AC 1 ms 384 KB
subtask1_05.txt AC 7 ms 384 KB
subtask1_06.txt WA 9 ms 384 KB
subtask1_07.txt AC 37 ms 512 KB
subtask1_08.txt WA 42 ms 512 KB
subtask1_09.txt AC 356 ms 512 KB
subtask1_10.txt AC 338 ms 512 KB
subtask1_11.txt AC 148 ms 512 KB
subtask1_12.txt WA 1096 ms 512 KB
subtask1_13.txt WA 1077 ms 512 KB
subtask1_14.txt WA 1184 ms 512 KB
subtask1_15.txt AC 813 ms 512 KB
subtask1_16.txt WA 1199 ms 512 KB