oj.uz

답안 #55393

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55393 2018-07-07T06:47:33 Z fefe 여행하는 상인 (APIO17_merchant) C++17
33 / 100
 113 ms 2380 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],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(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]);
		}
	}
	for(k=1;k<=n;k++){
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				dst[i][j]=min(dst[i][j],dst[i][k]+dst[k][j]);
			}
		}
	}
	for(i=1;i<=n;i++){
		if(dst[i][i]<=0)	return true;
	}
	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:73: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:76: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:88: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:88: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 113 ms 2296 KB Output is correct
2 Correct 78 ms 2296 KB Output is correct
3 Correct 79 ms 2296 KB Output is correct
4 Incorrect 12 ms 2296 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 2296 KB Output is correct
2 Correct 109 ms 2380 KB Output is correct
3 Correct 98 ms 2380 KB Output is correct
4 Correct 87 ms 2380 KB Output is correct
5 Correct 99 ms 2380 KB Output is correct
6 Correct 105 ms 2380 KB Output is correct
7 Correct 16 ms 2380 KB Output is correct
8 Correct 2 ms 2380 KB Output is correct
9 Correct 16 ms 2380 KB Output is correct
10 Correct 17 ms 2380 KB Output is correct
11 Correct 17 ms 2380 KB Output is correct
12 Correct 19 ms 2380 KB Output is correct
13 Correct 13 ms 2380 KB Output is correct

Subtask #4
0 / 34.0

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