oj.uz

답안 #679463

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
679463 2023-01-08T10:14:49 Z Warinchai Autobus (COCI22_autobus) C++14
0 / 70
 1000 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
vector<pair<long long,int> >ar[75][75];
long long mn[75][75];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			mn[i][j]=INT_MAX;
			if(i==j){
				ar[i][j].push_back({0,0});
				mn[i][j]=0;
			}
		}
	}
	for(int i=0;i<m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		ar[a][b].push_back({c,1});
		mn[a][b]=c;
	}
	int r,q,lgth;
	long long mnn=0;
	cin>>r>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				//cout<<i<<" "<<j<<" "<<k<<" info:"<<endl;
				if(j==i){
					continue;
				}
				//cout<<ar[i][k].size()<<' '<<ar[k][j].size()<<endl;
				if(ar[i][k].size()!=0&&ar[k][j].size()!=0){
				//	cout<<"qork \n";
					for(int l=0;l<ar[i][k].size();l++){
						for(int p=0;p<ar[k][j].size();p++){
						//	cout<<l<<" "<<p<<":";
							lgth=ar[i][k][l].second+ar[k][j][p].second;
							mnn=LLONG_MAX;
							for(int s=0;s<ar[i][j].size();s++){
								if(ar[i][j][s].second==lgth){
									mnn=ar[i][j][s].first;
									break;
								}
							}
						//	cout<<lgth<<" "<<mnn<<" "<<ar[i][k][l].first+ar[k][j][p].first<<"\n";
							if(ar[i][k][l].first+ar[k][j][p].first>=mnn){
								continue;
							}
							if(ar[i][k][l].second+ar[k][j][p].second<=r){
								//cout<<ar[i][k][l].second+ar[k][j][p].second<<" "<<ar[i][k][l].first+ar[k][j][p].first<<endl;
								ar[i][j].push_back({ar[i][k][l].first+ar[k][j][p].first,ar[i][k][l].second+ar[k][j][p].second});
								if(ar[i][k][l].first+ar[k][j][p].first<mn[i][j]){
									mn[i][j]=ar[i][k][l].first+ar[k][j][p].first;
								}
							}
						}
					}
				}
			}
		}
	}
	for(int i=0;i<q;i++){
		int a,b;
		cin>>a>>b;
		if(mn[a][b]==INT_MAX){
			cout<<"-1\n";
		}else{
			cout<<mn[a][b]<<"\n";
		}
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |      for(int l=0;l<ar[i][k].size();l++){
      |                  ~^~~~~~~~~~~~~~~~
Main.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |       for(int p=0;p<ar[k][j].size();p++){
      |                   ~^~~~~~~~~~~~~~~~
Main.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |        for(int s=0;s<ar[i][j].size();s++){
      |                    ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 538 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 15.0

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