#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,(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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
1912 KB |
Output is correct |
2 |
Incorrect |
5 ms |
1912 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
1912 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
1912 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
1912 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |