Submission #558459

Source Code Expand

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

#define NMAX (200+1)
#define PMAX 1000+1

typedef struct{
  int v,t,s;
} edg;

int N,M,P;
int a,b,v,t;
vector<edg> vec[NMAX];
double vmax[NMAX][PMAX];
queue<int> qt;
queue<int> qn;

int main(){

  cin>>N>>M>>P;

  for(int i=0;i<M;i++){
    cin>>a>>b>>t>>v;
    edg tmp;
    tmp.v=v,tmp.t=t,tmp.s=b;
    vec[a].push_back(tmp);
    tmp.s=a;
    vec[b].push_back(tmp);
  }

  for(int i=0;i<=N;i++){
    for(int j=0;j<=PMAX;j++){
      vmax[i][j]=-1;
    }
  }
  vmax[1][P]=0;

  qn.push(1);
  qt.push(P);
  while(!qn.empty()){
    int n=qn.front();
    int nt=qt.front();
    qn.pop();
    qt.pop();
    for(int i=0;i<vec[n].size();i++){
      if(nt-vec[n][i].t>=0){
	if(vmax[vec[n][i].s][nt-vec[n][i].t]<vmax[n][nt]+vec[n][i].v){
	  /*cout<<vmax[n][nt]<<","<<vmax[vec[n][i].s][nt-vec[n][i].t]<<","<<nt<<endl;*/
	  vmax[vec[n][i].s][nt-vec[n][i].t]=vmax[n][nt]+vec[n][i].v;
	  qn.push(vec[n][i].s);
	  qt.push(nt-vec[n][i].t);
	}
      }
      if(nt-2*vec[n][i].t<0){
	/*cout<<vmax[n][nt]<<endl;*/
	if(vmax[n][0]<(double)vmax[n][nt]+(nt)*((double)vec[n][i].v/vec[n][i].t)){
	  vmax[n][0]=(double)vmax[n][nt]+(nt)*((double)vec[n][i].v/vec[n][i].t);
	}
      }
    }
  }
  printf("%.10f\n",vmax[1][0]);
}

Submission Info

Submission Time
Task F - Marching Course
User MOTA
Language C++11 (GCC 4.8.1)
Score 0
Code Size 1359 Byte
Status WA
Exec Time 5046 ms
Memory 35980 KiB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 21
WA × 10
TLE × 21
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 10_complete_00, 10_complete_01, 10_complete_02, 10_complete_03, 10_complete_04, 11_complete_max_00, 11_complete_max_01, 11_complete_max_02, 11_complete_max_03, 11_complete_max_04, 20_rnd_00, 20_rnd_01, 20_rnd_02, 20_rnd_03, 20_rnd_04, 21_rnd_max_00, 21_rnd_max_01, 21_rnd_max_02, 21_rnd_max_03, 21_rnd_max_04, 30_sparse_00, 30_sparse_01, 40_star_00, 40_star_01, 50_uniform_00, 50_uniform_01, 51_almost_uniform_00, 51_almost_uniform_01, 60_hard_far_00, 60_hard_far_01, 60_hard_far_02, 60_hard_far_03, 60_hard_far_04, 61_hard_layer_00, 61_hard_layer_01, 61_hard_layer_02, 61_hard_layer_03, 61_hard_layer_04, 62_hard_chain_00, 62_hard_chain_01, 62_hard_chain_02, 62_hard_chain_03, 62_hard_chain_04, 99_handmade_00, 99_handmade_01, 99_handmade_02, 99_handmade_03, 99_handmade_04
Case Name Status Exec Time Memory
00_sample_00 AC 27 ms 924 KiB
00_sample_01 AC 27 ms 804 KiB
00_sample_02 AC 26 ms 804 KiB
00_sample_03 AC 26 ms 924 KiB
10_complete_00 WA 2193 ms 2976 KiB
10_complete_01 TLE 5040 ms 25804 KiB
10_complete_02 TLE 5036 ms 7332 KiB
10_complete_03 TLE 5038 ms 26556 KiB
10_complete_04 TLE 5035 ms 4124 KiB
11_complete_max_00 TLE 5041 ms 30748 KiB
11_complete_max_01 TLE 5038 ms 17244 KiB
11_complete_max_02 TLE 5043 ms 35980 KiB
11_complete_max_03 TLE 5038 ms 14252 KiB
11_complete_max_04 TLE 5040 ms 13716 KiB
20_rnd_00 WA 38 ms 1004 KiB
20_rnd_01 TLE 5038 ms 6948 KiB
20_rnd_02 WA 933 ms 1824 KiB
20_rnd_03 TLE 5036 ms 8740 KiB
20_rnd_04 AC 26 ms 1052 KiB
21_rnd_max_00 TLE 5039 ms 19020 KiB
21_rnd_max_01 TLE 5039 ms 13472 KiB
21_rnd_max_02 TLE 5038 ms 15780 KiB
21_rnd_max_03 TLE 5042 ms 21316 KiB
21_rnd_max_04 TLE 5046 ms 22200 KiB
30_sparse_00 AC 27 ms 1048 KiB
30_sparse_01 WA 29 ms 2076 KiB
40_star_00 AC 87 ms 2460 KiB
40_star_01 AC 53 ms 2592 KiB
50_uniform_00 AC 61 ms 2984 KiB
50_uniform_01 AC 64 ms 2976 KiB
51_almost_uniform_00 AC 86 ms 1184 KiB
51_almost_uniform_01 AC 378 ms 2844 KiB
60_hard_far_00 AC 472 ms 1312 KiB
60_hard_far_01 AC 705 ms 2332 KiB
60_hard_far_02 WA 668 ms 2092 KiB
60_hard_far_03 AC 245 ms 1632 KiB
60_hard_far_04 WA 232 ms 1560 KiB
61_hard_layer_00 TLE 5035 ms 4272 KiB
61_hard_layer_01 TLE 5037 ms 3804 KiB
61_hard_layer_02 TLE 5036 ms 3496 KiB
61_hard_layer_03 TLE 5036 ms 3492 KiB
61_hard_layer_04 TLE 5036 ms 3628 KiB
62_hard_chain_00 WA 3763 ms 4008 KiB
62_hard_chain_01 AC 1173 ms 3288 KiB
62_hard_chain_02 AC 1046 ms 2980 KiB
62_hard_chain_03 WA 1299 ms 3104 KiB
62_hard_chain_04 WA 334 ms 2976 KiB
99_handmade_00 AC 28 ms 920 KiB
99_handmade_01 AC 27 ms 796 KiB
99_handmade_02 AC 25 ms 796 KiB
99_handmade_03 WA 27 ms 924 KiB
99_handmade_04 AC 56 ms 804 KiB