Submission #1734850
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;
const int MAX_N = 2510;
using TYPE = ll; // 距離の型を入れる
vector<pair<ll, TYPE> > G[MAX_N];
vector<TYPE> dijkstra(int start){
vector<TYPE> dist(MAX_N, INFF);
dist[start] = 0;//dist[i] := start->iまでの最短距離
priority_queue<pair<TYPE, int>, vector<pair<TYPE, int> >, greater<pair<TYPE, int> > > que;
que.push(make_pair(0, start));
while(!que.empty()){
TYPE cost; int u;//今までにかかった時間 現在の頂点
cost = que.top().first, u = que.top().second;
que.pop();
if(dist[u] < cost) continue;
for (auto tmp : G[u]){
int v = tmp.first; TYPE time = tmp.second;//隣接する頂点 その頂点まで行く時間
if(dist[v] > dist[u] + time){//u->v
dist[v] = dist[u] + time;
que.push(make_pair(dist[v], v));
}
}
}
return dist;
}
int N, M, R, T;
int main(void) {
scanf("%d %d %d %d", &N, &M, &R, &T);
rep(i, M) {
int a, b, c; scanf("%d %d %d", &a, &b, &c);
a--; b--;
G[a].pb(mp(b, c)), G[b].pb(mp(a, c));
}
ll ans = 0;
rep(i, N) { // ゴールの位置
auto dist = dijkstra(i);
vector<double> vr, vt; // うさぎ かめ
rep(j, N) {
if(i == j) continue;
vr.push_back((double)dist[j] / (double)R);
vt.push_back((double)dist[j] / (double)T);
if(dist[j] / R == dist[j] / T) ans--;
}
sort(all(vr)), sort(all(vt));
for(auto k : vt) { // かめ
// printf("t %f\n", k);
ll cnt = (N - 1) - (upper_bound(all(vr), k) - vr.begin());
// printf("cnt %d\n", cnt);
ans += cnt;
}
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - ウサギとカメ |
User |
mmxsrup |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2276 Byte |
Status |
WA |
Exec Time |
1503 ms |
Memory |
512 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:49:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &N, &M, &R, &T);
^
./Main.cpp:51:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int a, b, c; scanf("%d %d %d", &a, &b, &c);
^
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 |
WA |
1 ms |
384 KB |
subtask1_01.txt |
WA |
1 ms |
384 KB |
subtask1_02.txt |
WA |
1 ms |
384 KB |
subtask1_03.txt |
WA |
1 ms |
384 KB |
subtask1_04.txt |
WA |
1 ms |
384 KB |
subtask1_05.txt |
AC |
9 ms |
384 KB |
subtask1_06.txt |
AC |
10 ms |
384 KB |
subtask1_07.txt |
WA |
32 ms |
512 KB |
subtask1_08.txt |
AC |
44 ms |
384 KB |
subtask1_09.txt |
WA |
433 ms |
512 KB |
subtask1_10.txt |
WA |
442 ms |
512 KB |
subtask1_11.txt |
WA |
171 ms |
512 KB |
subtask1_12.txt |
WA |
1430 ms |
512 KB |
subtask1_13.txt |
WA |
1425 ms |
512 KB |
subtask1_14.txt |
WA |
1502 ms |
512 KB |
subtask1_15.txt |
WA |
1003 ms |
512 KB |
subtask1_16.txt |
WA |
1503 ms |
512 KB |