Submission #556654

#	Time	Username	Problem	Language	Result	Execution time	Memory
556654		elesis	Autobus (COCI22_autobus)	C++14	70 / 70	425 ms	6912 KiB

Main

#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int up=1e6+7;
const int mod=1e9+7;
const int inf=1e9;
int binpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
		{
			res=(res*a)%mod;
		}
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}
int inv(int x)
{
	int res=binpow(x,mod-2);
	return res;
}
const int N=77;
vector <vector <int>> adj(N,vector <int> (N,inf));
void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		adj[i][i]=0;
	}
	for(int i=0;i<m;i++)
	{
		int u,v,e;
		cin>>u>>v>>e;
		adj[u][v]=min(adj[u][v],e);
	}
	//cout << adj[1][3] << "\n";
	int k,q;
	cin>>k>>q;
	k=min(k,n);
	k--;
	auto ans=adj;
	//cout << ans[1][4] << "\n";
	while(k--)
	{
		auto temp=ans;
		for(int x=1;x<=n;x++)
		{
			for(int y=1;y<=n;y++)
			{
				for(int z=1;z<=n;z++)
				{
					temp[x][y]=min(temp[x][y],ans[x][z]+adj[z][y]);
					//cout << temp[x][y] << " " << x << " " << y << "\n
				}
			}
		}
		ans=temp;
		//cout << temp[1][4] << "\n";
	}
	//cout << ans[1][4] << "\n";
	//cout << ans[1][4] << "\n";
	while(q--)
	{
		int u,v;
		cin>>u>>v;
		if(ans[u][v]>=inf)
		{
			cout << -1 << "\n";
		}
		else
		{
			cout << ans[u][v] << "\n";
		}
	}
}
signed main(){
	//fast
	clock_t start, end;
	start = clock();
	solve();
	end = clock();
	double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
	//cout << "time taken" << " " << time_taken << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:93:9: warning: unused variable 'time_taken' [-Wunused-variable]
   93 |  double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
      |         ^~~~~~~~~~

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