oj.uz

답안 #689825

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
689825 2023-01-29T12:53:29 Z Warinchai Autobus (COCI22_autobus) C++14
0 / 70
 1000 ms 7124 KB 
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >ar[75];
int mn[75][75][75];
void dfs(int x,int dis,int rt,int st){
	for(int i=0;i<ar[x].size();i++){
		if(dis+ar[x][i].second<mn[st][ar[x][i].first][rt+1]){
			mn[st][ar[x][i].first][rt+1]=dis+ar[x][i].second;
			dfs(ar[x][i].first,dis+ar[x][i].second,rt+1,st);
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<75;i++){
		for(int j=0;j<75;j++){
			for(int k=0;k<75;k++){
				mn[i][j][k]=INT_MAX;
				if(i==j){
					mn[i][j][k]=0;
				}
			}
		}
	}
	
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		ar[a].push_back({b,c});
	}
	int k,q;
	cin>>k>>q;
	if(k>n){
		k=n;
	}
	for(int i=1;i<=n;i++){
		dfs(i,0,0,i);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			int mnn=INT_MAX;
			for(int l=1;l<=k;l++){
				mnn=min(mnn,mn[i][j][l]);
			}
			mn[i][j][k]=mnn;
		}
	}
	/*for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int l=1;l<=k;l++){
				cout<<mn[i][j][l]<<" ";
			}
			cout<<endl;
		}
		cout<<"----------------------"<<endl;
	}*/
	for(int i=0;i<q;i++){
		int c,d;
		cin>>c>>d;
		if(mn[c][d][k]==INT_MAX){
			cout<<"-1\n";
		}else{
			cout<<mn[c][d][k]<<"\n";
		}
	}
}

Compilation message

Main.cpp: In function 'void dfs(int, int, int, int)':
Main.cpp:6:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |  for(int i=0;i<ar[x].size();i++){
      |              ~^~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 7124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 15.0

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