이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N=1e2+10;
const ll INF=1e18;
vector<pair<int,int> >graf[N];
pair<ll,int>pom[N][N];
ll curr[N][N];
bitset<N>vis;
pair<int,int>t[N][1001];
ll odl[N];
int n,m,k;
void Dijkstra(int xd){
for(int i=1;i<=n;i++) vis[i]=0;
set<pair<ll,int> >s;
s.insert({0,xd});
while(s.size()){
auto it=s.begin();
pair<ll,int> v=*it;
s.erase(it);
if(vis[v.se]) continue;
vis[v.se]=1;
odl[v.se]=v.fi;
for(auto [u,c]:graf[v.se]){
ll pom=c+v.fi;
if(!vis[u]) s.insert({pom,u});
}
}
}
bool check(ll x){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(pom[i][j].fi==-1) curr[i][j]=-INF;
else curr[i][j]=pom[i][j].se-pom[i][j].fi*x;
curr[i][j]*=(-1LL);
}
}
for(int sr=1;sr<=n;sr++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(curr[i][j]>curr[i][sr]+curr[sr][j] and curr[i][sr]!=INF and curr[sr][j]!=INF)
curr[i][j]=curr[i][sr]+curr[sr][j];
}
}
}
bool res=0;
for(int i=1;i<=n;i++) if(curr[i][i]<=0) res=1;
return res;
}
int bs(){
int res=0,kon=1e9,pocz=1,sr;
while(pocz<=kon){
sr=(pocz+kon)>>1;
if(check(sr)) res=sr,pocz=sr+1;
else kon=sr-1;
}
return res;
}
void solve(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++) cin>>t[i][j].fi>>t[i][j].se;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
graf[a].push_back({b,c});
}
for(int v=1;v<=n;v++){
Dijkstra(v);
for(int i=1;i<=n;i++){
if(!vis[i] or i==v) pom[v][i].fi=-1;
else{
pom[v][i].fi=odl[i];
for(int j=1;j<=k;j++) if(t[v][j].fi!=-1 and t[i][j].se!=-1) pom[v][i].se=max(pom[v][i].se,t[i][j].se-t[v][j].fi);
}
}
}
cout<<bs()<<"\n";
}
int main(){
ios_base::sync_with_stdio(0),cin.tie(0);
solve();
}
컴파일 시 표준 에러 (stderr) 메시지
merchant.cpp: In function 'void Dijkstra(int)':
merchant.cpp:26:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
26 | for(auto [u,c]:graf[v.se]){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |