oj.uz

답안 #402904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402904 2021-05-12T13:31:48 Z teehandsome 여행하는 상인 (APIO17_merchant) C++11
0 / 100
 21 ms 1124 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define buy first
#define sell second

const int mxn=102;
const int mxk=1010;
int n,m,k;

vector<pii> adj[mxn],adj2[mxn];
int dp[mxk];
pii shop[mxn][mxk];
int dist[mxn],dist2[mxn];

void dijk() {
    memset(dist,INF,sizeof(dist));
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    vector<bool> flag(n+1,false);
    dist[1]=0;
    pq.push({0,1});
    while(!pq.empty()) {
        pii cur=pq.top(); pq.pop();
        int d=cur.first,u=cur.second;
        flag[u]=true;
        for(auto vw:adj[u]) {
            int v=vw.first,w=vw.second;
            if(!flag[v] and d+w<dist[v]) {
                dist[v]=d+w;
                pq.push({dist[v],v});
            }
        }
    }
}

void dijk2() {
    memset(dist2,INF,sizeof(dist2));
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    vector<bool> flag(n+1,false);
    pq.push({0,1}); dist2[1]=0;
    while(!pq.empty()) {
        pii cur=pq.top(); pq.pop();
        int d=cur.first,u=cur.second;
        flag[u]=true;
        for(auto vw:adj2[u]) {
            int v=vw.first, w=vw.second;
            if(!flag[v] and d+w<dist2[v]) {
                dist2[v]=d+w;
                pq.push({dist2[v],v});
            }
        }
    }
}

int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=k;j++) {
            cin>>shop[i][j].buy>>shop[i][j].sell;
        }
    }
    for(int i=0;i<m;i++) {
        int u,v,w; cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj2[v].push_back({u,w});
    }
    dijk();
    dijk2();

    int ans=0;

    for(int i=2;i<=n;i++) {
        for(int j=1;j<=k;j++) {
            if(shop[i][j].sell==-1 or shop[1][j].buy==-1) continue;
            if(dist[i]==INF or dist2[i]==INF) continue;
            int val=(shop[i][j].sell-shop[1][j].buy)/(dist2[i]+dist[i]);
            ans=max(ans,(shop[i][j].sell-shop[1][j].buy)/(dist2[i]+dist[i]));
//            debug(i,j,val);
        }
    }

    cout<<ans<<endl;
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:105:17: warning: unused variable 'val' [-Wunused-variable]
  105 |             int val=(shop[i][j].sell-shop[1][j].buy)/(dist2[i]+dist[i]);
      |                 ^~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 1124 KB Output is correct
2 Incorrect 1 ms 716 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -