제출 #1326467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326467		JuanJL	Olympic Bus (JOI20_ho_t4)	C++20	5 / 100	162 ms	7752 KiB

ho_t4

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define forn(i,a,b) for(int i = a; i<b; i++)
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

#ifdef D
	#define debug(x) cout << x
#else
	#define debug(x) //nothing
#endif

const int MAXN = 200+5;
const int MAXM = 50000+5;

#define INF ((ll)20000000000000)

ll n,m;
vector<pair<ll,ll>> adj[MAXN];
ll cost[MAXM];
ll revc[MAXM];

pair<vector<ll>,vector<ll>> dijkstra(ll nd){
	vector<ll> dist(n,-1);
	vector<ll> pa(n,-1);
	priority_queue<pair<ll,pair<ll,ll>>> pq; pq.push({0,{nd,-1}});
	while(!pq.empty()){
		ll nd = pq.top().snd.fst;
		ll c = pq.top().fst*-1;
		ll p = pq.top().snd.snd;
		pq.pop();

		if(dist[nd]!=-1) continue;
		dist[nd]=c;
		pa[nd]=p;

		for(auto i:adj[nd]) if(i.snd>=0){
			pq.push({(c+cost[i.snd])*-1,{i.fst,nd}});
		}
	}

	return {dist,pa};
}


vector<ll> d1N;
vector<ll> p1N;
vector<ll> dN1;
vector<ll> pN1;

pair<ll,ll> ari[MAXM];
ll uind[MAXM];
ll vind[MAXM];
bool principal[MAXM];

void calcprincipal(){
	ll nd = n-1;
	while(p1N[nd]!=-1){
		forn(j,0,SZ(adj[p1N[nd]])){
			if(adj[p1N[nd]][j].fst==nd){
				principal[adj[p1N[nd]][j].snd]=true;
			}
		}
		nd=p1N[nd];
	}

	nd = 0;
	while(pN1[nd]!=-1){
		forn(j,0,SZ(adj[pN1[nd]])){
			if(adj[pN1[nd]][j].fst==nd){
				principal[adj[pN1[nd]][j].snd]=true;
			}
		}
		nd=pN1[nd];
	}
}

int main(){
	cin>>n>>m;

	ll u,v;
	forn(i,1,m+1){
		cin>>u>>v; u--; v--;
		uind[i]=SZ(adj[u]);
		vind[i]=SZ(adj[v]);
		adj[u].pb({v,i}); ari[i]={u,v};
		adj[v].pb({u,-i});
		cin>>cost[i];
		cin>>revc[i];
	}

	d1N = dijkstra(0).fst;
	p1N = dijkstra(0).snd;
	dN1 = dijkstra(n-1).fst;
	pN1 = dijkstra(n-1).snd;

	calcprincipal();
	
	ll res = -1;
	if(d1N[n-1]!=-1 && dN1[0]!=-1) res=d1N[n-1]+dN1[0];

	forn(i,0,n){
		for(auto j:adj[i]) debug(i<<"->"<<j.fst<<" "<<j.snd<<'\n');
	}
		
	forn(i,1,m+1){
		if(principal[i]||true){
			ll cost = revc[i];
			adj[ari[i].fst][uind[i]].snd*=-1;
			adj[ari[i].snd][vind[i]].snd*=-1;

			vector<ll> aux1N = dijkstra(0).fst;
			vector<ll> auxN1 = dijkstra(n-1).fst;

			debug("dbg "<<aux1N[n-1]<<" "<<auxN1[0]<<'\n');
			
			if(aux1N[n-1]!=-1 && auxN1[0]!=-1) cost+=aux1N[n-1]+auxN1[0];
			else cost+=INF;

			adj[ari[i].fst][uind[i]].snd*=-1;
			adj[ari[i].snd][vind[i]].snd*=-1;

			if((res==-1 || res>cost)&&cost<INF) res=cost;
		}
	}	

	cout<<res<<'\n';
	return 0;
}

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