oj.uz

답안 #229170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
229170 2020-05-03T14:48:22 Z laoriu 여행하는 상인 (APIO17_merchant) C++14
0 / 100
 101 ms 3064 KB 
#include <bits/stdc++.h>
using namespace std;
const double ll=1e-9;
typedef pair <int,int> pp;
int n,m,k,S[102][1002],B[102][1002];
int c[102][102],d[102][102];
double cost[102][102],s[102];
vector <pp> A[102];
void prepare()
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            c[i][j]=0;
            for (int x=1;x<=k;x++)
                if (B[i][x]!=-1&&S[j][x]!=-1) c[i][j]=max(c[i][j],S[j][x]-B[i][x]);
        }
    for (int x=1;x<=n;x++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                d[i][j]=min(d[i][j],d[i][x]+d[x][j]);
    //for (int i=1;i<=n;i++)
       // for (int j=1;j<=n;j++)
       // cout<<i<<' '<<j<<' '<<d[i][j]<<' '<<c[i][j]<<endl;
}
int check(int x)
{
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i!=j) cost[i][j]=(double) x*d[i][j]-c[i][j]-ll;
   /* cout<<"cac "<<x<<endl;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            cout<<i<<' '<<j<<' '<<cost[i][j]<<endl;*/
    for (int i=1;i<=n;i++)
        s[i]=cost[1][i];
    for (int x=1;x<=n;x++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (s[j]>s[i]+cost[i][j]) s[j]=s[i]+cost[i][j];
    for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                if (s[j]>s[i]+cost[i][j]) return 1;
    return 0;
}
void solve()
{
    //cout<<fixed<<setprecision(10)<<ll<<endl;
    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++)
            if (i!=j) d[i][j]=1e9;
    for (int i=1;i<=m;i++)
    {
        int a,b,c;cin>>a>>b>>c;
        A[a].push_back({b,c});
        d[a][b]=min(d[a][b],c);
    }
    prepare();
    int d=0;int c=1e9;
    int res=0;
    while (d<=c)
    {
        int mid=(d+c)/2;
        if (check(mid)) {res=mid;d=mid+1;}
        else c=mid-1;
    }
    cout<<res;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("merchant.inp","r",stdin);
    //freopen("merchant.out","w",stdout);
    solve();
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 2560 KB Output is correct
2 Correct 37 ms 1280 KB Output is correct
3 Correct 39 ms 1280 KB Output is correct
4 Correct 9 ms 768 KB Output is correct
5 Correct 10 ms 768 KB Output is correct
6 Correct 11 ms 896 KB Output is correct
7 Correct 11 ms 896 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 10 ms 896 KB Output is correct
10 Incorrect 10 ms 896 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct
3 Correct 11 ms 896 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 11 ms 896 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 768 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 10 ms 896 KB Output is correct
10 Correct 11 ms 896 KB Output is correct
11 Correct 12 ms 896 KB Output is correct
12 Incorrect 11 ms 768 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 1632 KB Output is correct
2 Correct 101 ms 3064 KB Output is correct
3 Correct 43 ms 1408 KB Output is correct
4 Correct 48 ms 1536 KB Output is correct
5 Correct 45 ms 1536 KB Output is correct
6 Correct 43 ms 1408 KB Output is correct
7 Correct 11 ms 896 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 11 ms 928 KB Output is correct
10 Incorrect 11 ms 896 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct
3 Correct 11 ms 896 KB Output is correct
4 Correct 11 ms 896 KB Output is correct
5 Correct 11 ms 896 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 10 ms 768 KB Output is correct
8 Correct 10 ms 896 KB Output is correct
9 Correct 10 ms 896 KB Output is correct
10 Correct 11 ms 896 KB Output is correct
11 Correct 12 ms 896 KB Output is correct
12 Incorrect 11 ms 768 KB Output isn't correct
13 Halted 0 ms 0 KB -