Submission #689975

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
689975	2023-01-30 00:07:19	EthanKim8683	Toll (BOI17_toll)	C++17	100 / 100	162 ms	36104 KiB

toll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
using I=int;
using B=bool;
const I N=50000;
const I K=5;
const I LOGN=16;
const I MAX=1e9;
vector<I>adjs[N];
pair<I,I>ancs[N][LOGN][K];
pair<I,I>tmps[2][K];
I main(){
  cin.tie(0)->sync_with_stdio(0);
  fill(&ancs[0][0][0],&ancs[0][0][0]+N*LOGN*K,pair<I,I>{MAX,-1});
  I k,n,m,o;cin>>k>>n>>m>>o;
  for(I i=0;i<m;i++){
    I a,b,t;cin>>a>>b>>t;
    ancs[a][0][b%k]={t,b};
  }
  for(I i=1;i<LOGN;i++)for(I j=0;j<n;j++){
    for(I x=0;x<k;x++){
      auto[d1,a]=ancs[j][i-1][x];
      if(a==-1)continue;
      for(I y=0;y<k;y++){
        auto[d2,b]=ancs[a][i-1][y];
        if(b==-1)continue;
        ancs[j][i][y]=min(ancs[j][i][y],{d1+d2,b});
      }
    }
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44