Submission #679463

#	Time	Username	Problem	Language	Result	Execution time	Memory
679463		Warinchai	Autobus (COCI22_autobus)	C++14	0 / 70	1083 ms	524288 KiB

Main

#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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15