oj.uz

Submission #68629

# Submission time Handle Problem Language Result Execution time Memory
68629 2018-08-17T17:15:59 Z KLPP Travelling Merchant (APIO17_merchant) C++14
0 / 100
 99 ms 2040 KB 
#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=0;
	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,(2*table[i][j].second-2*table[0][j].first+1)/(2*dist[i][0]+2*dist[0][i]));
//cout<<ans<<" "<<i<<" "<<j<<endl;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -