oj.uz

답안 #556534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556534 2022-05-03T10:08:31 Z elesis Autobus (COCI22_autobus) C++14
0 / 70
 9 ms 456 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:13: warning: unused variable 'time_taken' [-Wunused-variable]
   89 |      double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
      |             ^~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 340 KB Output is correct
2 Incorrect 9 ms 456 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -