Submission #703965

#	Time	Username	Problem	Language	Result	Execution time	Memory
703965		willychan	Autobus (COCI22_autobus)	C++14	70 / 70	106 ms	6940 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds

vector<vector<ll> > dis;
int n,m;
vector<vector<ll> > ans;
void pow(int p) {
    ans.resize(n);
    for(int i=0; i<n; i++) ans[i].resize(n,1e17);
	for(int i=0;i<n;i++) ans[i][i]=0;
	vector<vector<ll> > og;
    while(p) {
        if(p&1) {
			og = ans;
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    for(int k=0; k<n; k++) {
                        og[i][j] = min(og[i][j],ans[i][k]+dis[k][j]);
                    }
                }
            }
            ans = og;
        }
		og = dis;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                for(int k=0; k<n; k++) {
                    og[i][j] = min(og[i][j],dis[i][k]+dis[k][j]);
                }
            }
        }
		dis = og;
		p>>=1;
    }


}


int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    dis.resize(n);
    for(int i=0; i<n; i++) dis[i].resize(n,1e17);
    for(int i=0; i<n; i++) dis[i][i]=0;
    for(int i=0; i<m; i++) {
        ll a,b,c;
        cin>>a>>b>>c;
		a--;b--;
        dis[a][b] = min(dis[a][b],c);
    }
	int k,q;cin>>k>>q;
	pow(k);
	while(q--){
		int a,b;cin>>a>>b;
		a--;b--;
		if(ans[a][b]>5e16){
			cout<<-1<<"\n";
		}else{
			cout<<ans[a][b]<<"\n";
		}
	}


    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15