oj.uz

Submission #556532

# Submission time Handle Problem Language Result Execution time Memory
556532 2022-05-03T10:06:38 Z elesis Autobus (COCI22_autobus) C++14
0 / 70
 10 ms 636 KB 
#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);
	}
	auto maboi=adj;
	auto fin=adj;
	//waaaaaaaaarsaaaaaal
	int k,q;
	cin>>k>>q;
	k=min(k,n);
	while(--k)
	{
		maboi=fin;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				for(int k=1;k<=n;k++)
				{
					maboi[i][j]=(maboi[i][j],maboi[i][k]+maboi[k][j]);
				}	
			}
		}
		fin=maboi;
	}
	
	while(q--)
	{
		int u,v;
		cin>>u>>v;
		if(fin[u][v]==inf)
		{
			cout << -1 << "\n";
		}
		else
		{
			cout << fin[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

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 636 KB Output is correct
2 Incorrect 9 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -