제출 #446443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446443		jamezzz	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	417 ms	4156 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

#define int long long

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789123456789ll
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define maxn 205
#define maxm 50005

int n,m,u[maxm],v[maxm],c[maxm],d[maxm],dd[maxn];
int dist[maxn][maxn];
vi AL[maxn];
priority_queue<ii,vector<ii>,greater<ii>> pq;

int dij(int s,int t){
	for(int i=0;i<n;++i)dd[i]=INF;
	dd[s]=0;pq.push(ii(0,s));
	while(!pq.empty()){
		ii pr=pq.top();pq.pop();
		if(dd[pr.se]<pr.fi)continue;
		for(int i:AL[pr.se]){
			if(dd[v[i]]>dd[u[i]]+c[i]){
				dd[v[i]]=dd[u[i]]+c[i];
				pq.push(ii(dd[v[i]],v[i]));
			}
		}
	}
	return dd[t];
}

int32_t main(){
	sf("%lld%lld",&n,&m);
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(i!=j)dist[i][j]=INF;
		}
	}
	for(int i=0;i<m;++i){
		sf("%lld%lld%lld%lld",&u[i],&v[i],&c[i],&d[i]);
		--u[i];--v[i];
		mnto(dist[u[i]][v[i]],c[i]);
		AL[u[i]].pb(i);
	}
	for(int k=0;k<n;++k){
		for(int i=0;i<n;++i){
			for(int j=0;j<n;++j){
				mnto(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
	int ans=min(INF,dist[0][n-1]+dist[n-1][0]);
	for(int i=0;i<m;++i){
		int d1=min(dist[0][n-1],dist[0][v[i]]+c[i]+dist[u[i]][n-1]);
		int d2=min(dist[n-1][0],dist[n-1][v[i]]+c[i]+dist[u[i]][0]);
		if(d1+d2+d[i]<ans){
			AL[u[i]].erase(find(all(AL[u[i]]),i));
			AL[v[i]].pb(i);
			swap(u[i],v[i]);
			mnto(ans,dij(0,n-1)+dij(n-1,0)+d[i]);
			swap(u[i],v[i]);
			AL[u[i]].pb(i);
			AL[v[i]].pop_back();
		}
	}
	if(ans==INF)ans=-1;
	pf("%lld\n",ans);
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'int32_t main()':
ho_t4.cpp:57:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  sf("%lld%lld",&n,&m);
      |    ^
ho_t4.cpp:64:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   sf("%lld%lld%lld%lld",&u[i],&v[i],&c[i],&d[i]);
      |     ^

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63