제출 #363684

#제출 시각아이디문제언어결과실행 시간메모리
363684bigDuck여행하는 상인 (APIO17_merchant)C++14
12 / 100
184 ms3436 KiB
#include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount #define int ll int t, n, m, k, a[300010], q, l, r; int b[101][1001], s[101][1001]; int c[101][101]; int d[101][101]; int p[101][101]; vector<pii> g[101]; void dijkstra(int s){ multiset<pii> ms; ms.insert({0, s}); d[s][s]=0; bool v[101]; memset(v, 0, sizeof(v)); while(!ms.empty()){ int nod=(ms.begin())->sc; ms.erase(ms.begin()); v[nod]=true; for(pii pr:g[nod]){ int u=pr.ft, c=pr.sc; if(v[u]){continue;} auto it=ms.find({d[s][u], u}); if(it==ms.end()){ d[s][u]=d[s][nod]+c; ms.insert({d[s][u], u}); } else{ if(d[s][u]>(d[s][nod]+c) ){ ms.erase(it); d[s][u]=d[s][nod]+c; ms.insert({d[s][u], u}); } } } } } void build(int r){ for(int i=1; i<=n; i++){ g[i].clear(); } for(int i=1; i<=n; i++){ for(int j=1; j<=n;j++){ if(d[i][j]>0){ g[i].pb({j, r*d[i][j]-p[i][j]}); } } } } vector<int> g2[101]; int v2[101]; bool dfs(int s){ v2[s]=1; bool b=false; for(int u:g2[s]){ if(v2[u]==1){ v2[s]=-1; return true;} if(v2[u]==-1){continue;} b=(b||dfs(u)); } v2[s]=-1; return b; } bool BellmanFord(int r){ build(r); int d[101]; memset(d, 0, sizeof(d)); bool v[101]; memset(v, 0, sizeof(v)); v[1]=true; for(int i=1; i<n; i++){ for(int j=1; j<=n; j++){ if(!v[j]){continue;} for(auto pr:g[j]){ int u=pr.ft, c=pr.sc; if(v[u]){ d[u]=min(d[u], d[j]+c); } else{ d[u]=d[j]+c; v[u]=true; } } } } for(int i=1; i<=n; i++){ v2[i]=0; g2[i].clear(); } bool exists=false; for(int j=1; j<=n; j++){ if(!v[j]){continue;} for(auto pr:g[j]){ int u=pr.ft, c=pr.sc; if(v[u]){ if( (d[j]+c)<d[u] ){ exists=true; } if( (d[j]+c)==d[u] ){ g2[j].pb(u); } d[u]=min(d[u], d[j]+c); } else{ d[u]=d[j]+c; v[u]=true; } } } for(int i=1; i<=n; i++){ if(!v2[i]){exists=exists||dfs(i);} } for(int i=1; i<=n; i++){ v2[i]=0; g2[i].clear(); } return exists; } int32_t main(){ INIT 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<=m; i++){ int u, v, C; cin>>u>>v>>C; c[u][v]=C; g[u].pb({v, C}); } for(int i=1;i<=n; i++){ dijkstra(i); } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ //p[i][j]=-1; if(d[i][j]>0){ for(int l=1; l<=k; l++){ if( (s[j][l]>=0) && (b[i][l]>=0) ){ p[i][j]=max(p[i][j], s[j][l]-b[i][l]); } } } } } int l=1, r=1000000000, m=(l+r)>>1ll; while(l<r){ m=(l+r)>>1ll; if(BellmanFord(m)){ l=m+1; } else{ r=m; } m=(l+r)>>1ll; } cout<<(m-1); //cout<<BellmanFord(m)<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...