Submission #1162880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162880		irmuun	Olympic Bus (JOI20_ho_t4)	C++20	11 / 100	12 ms	3400 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define pll pair<ll,ll>

const ll N=2e2,M=5e4;

ll n,m;
vector<ll>g[N],dist(N);

struct Edge{
	ll a,b,c,d;
	Edge():a(-1),b(-1),c(-1),d(-1){}
};

Edge edge[M];

ll dijkstra(ll s,ll t){
	fill(all(dist),(ll)1e18);
	dist[s]=0;
	priority_queue<pll,vector<pll>,greater<pll>>pq;
	pq.push({0,s});
	while(!pq.empty()){
		auto [D,x]=pq.top();
		pq.pop();
		if(dist[x]!=D) continue;
		if(x==t) return dist[x];
		for(ll i:g[x]){
			if(edge[i].a==x){
				if(dist[x]+edge[i].c<dist[edge[i].b]){
					dist[edge[i].b]=dist[x]+edge[i].c;
					pq.push({dist[edge[i].b],edge[i].b});
				}
			}
		}
	}
	return (ll)1e18;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(ll i=0;i<m;i++){
		cin>>edge[i].a>>edge[i].b>>edge[i].c>>edge[i].d;
		edge[i].a--;
		edge[i].b--;
		g[edge[i].a].pb(i);
		g[edge[i].b].pb(i);
	}
	dijkstra(0,-1);//0 ->
	auto d1=dist;
	dijkstra(n-1,-1);//n-1 ->
	auto d2=dist;
	for(ll i=0;i<m;i++){
		swap(edge[i].a,edge[i].b);
	}
	dijkstra(0,-1);//0 <-
	auto d3=dist;
	dijkstra(n-1,-1);//n-1 <-
	auto d4=dist;
	ll ans=d1[n-1]+d3[n-1];
	for(ll i=0;i<m;i++){
		ll x=min({d1[n-1],d1[edge[i].a]+d4[edge[i].b]+edge[i].c,d1[edge[i].b]+d4[edge[i].a]+edge[i].c});
		ll y=min({d2[0],  d2[edge[i].a]+d3[edge[i].b]+edge[i].c,d2[edge[i].b]+d3[edge[i].a]+edge[i].c});
		ans=min(ans,x+y+edge[i].d);
	}
	if(ans>=(ll)1e18) ans=-1;
	cout<<ans;
}

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