oj.uz

답안 #55392

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55392 2018-07-07T06:42:50 Z fefe 여행하는 상인 (APIO17_merchant) C++17
0 / 100
 338 ms 4252 KB 
#include<bits/stdc++.h>
//#include<inttypes.h>//__int64,__int128..
#define MAX_N 105
#define MAX_K 1005
//vector&pair
#define pb push_back
#define mp make_pair
//math
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))//Regardless of type
//for pair
#define fi first
#define se second
//infinit
#define inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
//MOD
#define MOD 1000000007LL*/
using namespace std;
//type
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef long double LD;
struct im{
	LL b,s;
}pd[MAX_N][MAX_K];
LL n,m,c;
LL net[MAX_N][MAX_N],dst[MAX_N][MAX_N],val[MAX_N],rev[MAX_N][MAX_N];
bool is_ok(LL K){
	LL i,j,k;
	//printf("%lld\n",K);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j)	dst[i][j]=inf;
			else if(net[i][j]==-1)	dst[i][j]=inf;
			else	dst[i][j]=K*net[i][j]-rev[i][j];
			//printf("%lld %lld : %lld\n",i,j,dst[i][j]);
		}
		val[i]=0;
	}
	for(i=1;i<=3*n;i++){
		for(j=1;j<=n;j++){
			for(k=1;k<=n;k++){
				if(dst[j][k]==inf)	continue;
				if(i>2*n && val[k]>val[j]+dst[j][k])	return true;
				val[k]=min(val[k],val[j]+dst[j][k]);
			}
		}
	}
	return false;
}
LL bin(){
	LL s,e,mid;
	bool x;
	s=1;
	e=1000000000;
	while(s<=e){
		mid=(s+e)>>1;
		x=is_ok(mid);
		if(x){
			if(!is_ok(mid+1))	return mid;
			s=mid+1;
		}else{
			if(is_ok(mid-1))	return mid-1;
			e=mid-1;
		}
	}
	return 0;
}
int main(){
	LL i,j,k,s,e;
	scanf("%lld %lld %lld",&n,&m,&c);
	for(i=1;i<=n;i++){
		for(j=1;j<=c;j++){
			scanf("%lld %lld",&pd[i][j].b,&pd[i][j].s);
			if(pd[i][j].b==-1)	pd[i][j].b=inf;
			if(pd[i][j].s==-1)	pd[i][j].s=-inf;
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			net[i][j]=-1;
			if(i==j)	continue;
			for(k=1;k<=c;k++)	rev[i][j]=max(rev[i][j],pd[j][k].s-pd[i][k].b);
		}
	}
	for(i=1;i<=m;i++){scanf("%lld %lld",&s,&e);scanf("%lld",&net[s][e]);}
	//Floyd-Warshall
	for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++){
		if(i==j || net[i][k]==-1 || net[k][j]==-1)	continue;
		net[i][j]=min(net[i][j],net[i][k]+net[k][j]);
	}	
	/*for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			printf("%lld %lld : %lld %lld\n",i,j,net[i][j],rev[i][j]);
		}
	}*/
	printf("%lld\n",bin());
	return 0;
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld %lld",&n,&m,&c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:77:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld %lld",&pd[i][j].b,&pd[i][j].s);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:89:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=m;i++){scanf("%lld %lld",&s,&e);scanf("%lld",&net[s][e]);}
                    ~~~~~^~~~~~~~~~~~~~~~~~~
merchant.cpp:89:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1;i<=m;i++){scanf("%lld %lld",&s,&e);scanf("%lld",&net[s][e]);}
                                             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 2288 KB Output is correct
2 Correct 233 ms 2288 KB Output is correct
3 Correct 253 ms 2288 KB Output is correct
4 Incorrect 37 ms 2288 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 2288 KB Output is correct
2 Correct 338 ms 4252 KB Output is correct
3 Correct 281 ms 4252 KB Output is correct
4 Correct 240 ms 4252 KB Output is correct
5 Incorrect 172 ms 4252 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

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