| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 677338 | MasterTaster | 여행하는 상인 (APIO17_merchant) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
#define MAXN 110
#define MAXK 1010
#define INF LLONG_MAX/2
using namespace std;
int n, m, k;
ll b[MAXN][MAXK], s[MAXN][MAXK], dist[MAXN][MAXN], p[MAXN][MAXN], novi[MAXN][MAXN], ress;
void fw(ll d[MAXN][MAXN])
{
for (int l=1; l<=n; l++)
{
for (int u=1; u<=n; u++)
{
for (int v=1; v<=n; v++)
{
d[u][v]=min(d[u][v], d[u][l]+d[l][v]);
}
}
}
}
int main() {
cin>>n>>m>>k;
for (int i=1; i<=n; i++) for (int j=1; j<=k; j++) cin>>b[i][j]>>s[i][j];
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dist[i][j]=INF;
for (int i=0; i<m; i++)
{
ll u, v, w; cin>>u>>v>>w;
dist[u][v]=w;
}
fw(dist);
/*for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
cout<<i<<" "<<j<<" "<<dist[i][j]<<endl;
}
}*/
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
for (int l=1; l<=k; l++)
{
if (b[i][l]==-1 || s[j][l]==-1) continue;
p[i][j]=max(p[i][j], s[j][l]-b[i][l]);
}
//cout<<i<<" "<<j<<" "<<p[i][j]<<endl;
}
}
ll l=0, r=1000000000LL;
while (l<=r)
{
ll mid=l+(r-l)/2;
//cout<<mid<<endl;
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++)
{
if (dist[i][j]==INF) novi[i][j]==INF-p[i][j];///-p
novi[i][j]=dist[i][j]*mid-p[i][j];
}
fw(novi);
bool moze=false;
for (int i=1; i<=n; i++) if (novi[i][i]<=0) moze=true;
if (moze)
{
ress=mid;
l=mid+1;
}
else
r=mid-1;
}
cout<<ress;
}