Submission #68624

#	Time	Username	Problem	Language	Result	Execution time	Memory
68624		KLPP	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	86 ms	3192 KiB

merchant

#include<iostream>
#include<vector>
#include<queue>

using namespace std;
typedef long long int lld;
#define INF 1000000000000000000

int main(){
	int n,m,k;
	cin>>n>>m>>k;
	lld dist[n][n];
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dist[i][j]=INF;
		}dist[i][i]=0;
	}
	pair<lld,lld> table[n][k];
	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			cin>>table[i][j].first>>table[i][j].second;
		}
	}
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		lld z;
		cin>>z;
		dist[x][y]=z;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<n;k++){
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
	/*for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout<<dist[i][j]<<" ";
		}cout<<endl;
	}*/
	lld ans=1;
	for(int i=1;i<n;i++){
		for(int j=0;j<k;j++){
			if(table[i][j].second!=-1 && table[0][j].first!=-1){
ans=max(ans,(table[i][j].second-table[0][j].first)/(dist[i][0]+dist[0][i]));
//cout<<ans<<" "<<i<<" "<<j<<endl;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34